Submission #11105

#	Time	Username	Problem	Language	Result	Execution time	Memory
11105		gs14004	Three Friends (BOI14_friends)	C++98	0 / 100	8 ms	10852 KiB

friends

#include <cstdio>
#include <cstdlib>

int n;
char str[2000005];

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

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] * 3141592;
    }
}

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(int l_hash, int 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(int l_hash, int 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 / 35
• Subtask 2: 0 / 65