oj.uz

Submission #11106

# Submission time Handle Problem Language Result Execution time Memory
11106 2014-11-13T15:16:53 Z gs14004 Three Friends (BOI14_friends) C++
0 / 100
 20 ms 18664 KB 
#include <cstdio>
#include <cstdlib>

int n;
char str[2000005];

long long pow[2000005], l_hash, r_hash;
int result = -1;

void input(){
    scanf("%d %s",&n,str);
    if(!(n&1)){
        puts("NOT POSSIBLE");
        exit(0);
    }
    pow[0] = 1;
    for (int i=1; i<n; i++) {
        pow[i] = pow[i-1] * 697;
    }
}

void output(){
    if(result == -1) puts("NOT POSSIBLE");
    else{
        int p = 0;
        for (int i=0; i<n/2+p; i++) {
            if(i == result){
                p++;
                continue;
            }
            putchar(str[i]);
        }
    }
}

void calc_left(long long l_hash, long long r_hash){
    int piv = 0;
    for (int i=n/2-1; i>=0; i--) {
        l_hash -= (str[i] - 'A') * pow[piv];
        l_hash += (str[i+1] - 'A') * pow[piv];
        if(l_hash == r_hash){
            if(~result){
                puts("NOT UNIQUE");
                exit(0);
            }
            else result = i;
        }
        piv++;
    }
}

void calc_right(long long l_hash, long long r_hash){
    int piv = n/2-1;
    for (int i=n/2+1; i<n; i++) {
        r_hash -= (str[i] - 'A') * pow[piv];
        r_hash += (str[i-1] -'A') * pow[piv];
        if(l_hash == r_hash){
            if(~result){
                puts("NOT UNIQUE");
                exit(0);
            }
            else result = i;
        }
        piv--;
    }
}

int main(){
    input();
    for (int i=0; i<n/2; i++) {
        l_hash *= 3141592;
        r_hash *= 3141592;
        l_hash += str[i] - 'A';
        r_hash += str[n/2 + 1 + i] - 'A';
    }
    if(l_hash == r_hash) result = n/2;
    calc_left(l_hash,r_hash);
    calc_right(l_hash,r_hash);
    output();
}

Subtask #1
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 18664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 18664 KB Output isn't correct
2 Halted 0 ms 0 KB -