Submission #1140940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140940		dpsaveslives	Three Friends (BOI14_friends)	C++20	100 / 100	21 ms	5352 KiB

friends

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6+5;
char arr[MAXN];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N; cin >> N;
    string U; cin >> U;
    if(N % 2 == 0){
        cout << "NOT POSSIBLE\n";
        return 0;
    }
    for(int i = 0;i<N;++i){
        arr[i+1] = U[i];
    }
    int cnt = 0, upp = (N+1)/2;
    for(int i = 2;i<=upp;++i){
        if(arr[i] == arr[i+upp-1]){
            ++cnt;
        }
    }
    int pos1 = -1;
    if(cnt == upp-1){
        pos1 = 1;
    }
    for(int i = 2;i<=upp-1;++i){
        if(arr[i-1] == arr[upp+i-1]){
            ++cnt;
        }
        if(arr[i] == arr[upp+i-1]){
            --cnt;
        }
        if(cnt == upp-1){
            pos1 = i;
            break;
        }
    }
    cnt = 0; int pos2 = -1;
    for(int i = 1;i<=upp-1;++i){
        if(arr[i] == arr[upp+i]){
            ++cnt;
        }
    }
    if(cnt == upp-1){
        pos2 = upp;
    }
    for(int i = upp+1;i<=N;++i){
        if(arr[i-upp] == arr[i-1]){
            ++cnt;
        }
        if(arr[i-upp] == arr[i]){
            --cnt;
        }
        if(cnt == upp-1){
            pos2 = i;
            break;
        }
    }
    if(pos1 != -1 && pos2 != -1){
        bool same = true;
        for(int i = 1;i<=upp-1;++i){
            if(arr[i] != arr[upp+i]){
                same = false;
            }
        }
        if(same){
            for(int i = 1;i<=upp-1;++i){
                cout << arr[i];
            }
            cout << "\n";
        }
        else{
            cout << "NOT UNIQUE\n";
        }
    }
    else if(pos1 != -1){
        for(int i = upp+1;i<=N;++i){
            cout << arr[i];
        }
        cout << "\n";
    }
    else if(pos2 != -1){
        for(int i = 1;i<=upp-1;++i){
            cout << arr[i];
        }
        cout << "\n";
    }
    else{
        cout << "NOT POSSIBLE\n";
    }
    return 0;
}

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