Submission #11108

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

friends

#include <cstdio>
#include <cstdlib>

int n,res = -1;
char str[2000005];

void upload(int x){
    if(~res){
        puts("NOT UNIQUE");
        exit(0);
    }
    res = x;
}

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

void calc_m(){
    for (int i=0; i<n/2; i++) {
        if(str[i] != str[i+n/2+1]) return;
    }
    res = n/2;
}

char s1[1000004], s2[1000004], diff[1000004], cnt;

void calc_l(){
    cnt = 0;
    for (int i=0; i<n/2; i++) {
        s1[i] = str[i];
        s2[i] = str[i+n/2+1];
        diff[i] = (s1[i] != s2[i]);
        cnt += diff[i];
    }
    for (int i=n/2-1; i>=0; i--) {
        s1[i] = str[i+1];
        if(s1[i] == s2[i] && diff[i]){
            diff[i] = 0;
            cnt--;
        }
        if(s1[i] != s2[i] && !diff[i]){
            diff[i] = 1;
            cnt++;
        }
        if(cnt == 0) upload(i);
    }
}

void calc_r(){
    cnt = 0;
    for (int i=0; i<n/2; i++) {
        s1[i] = str[i];
        s2[i] = str[i+n/2+1];
        diff[i] = (s1[i] != s2[i]);
        cnt += diff[i];
    }
    for (int i=n/2+1; i<n; i++) {
        s2[i-n/2-1] = str[i-1];
        if(s1[i-n/2-1] == s2[i-n/2-1] && diff[i-n/2-1]){
            diff[i-n/2-1] = 0;
            cnt--;
        }
        if(s1[i-n/2-1] != s2[i-n/2-1] && !diff[i-n/2-1]){
            diff[i-n/2-1] = 1;
            cnt++;
        }
        if(cnt == 0) upload(i);
    }
}

int main(){
    scanf("%d %s",&n,str);
    if(!(n&1)){
        puts("NOT POSSIBLE");
        exit(0);
    }
    calc_m();
    calc_l();
    calc_r();
    output();
}

• Subtask 1: 0 / 35
• Subtask 2: 0 / 65