Submission #1140937

#TimeUsernameProblemLanguageResultExecution timeMemory
1140937dpsaveslivesThree Friends (BOI14_friends)C++20
0 / 100
21 ms5352 KiB
#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;
        }
    }
    bool found = false; int pos = -1;
    if(cnt == upp-1){
        found = true;
        pos = 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){
            if(found){
                cout << "NOT UNIQUE\n";
                return 0;
            }
            else{
                found = true;
                pos = i;
            }
        }
    }
    cnt = 0;
    for(int i = 1;i<=upp-1;++i){
        if(arr[i] == arr[upp+i]){
            ++cnt;
        }
    }
    if(cnt == upp-1){
        if(found){
            cout << "NOT UNIQUE\n";
            return 0;
        }
        else{
            found = true;
            pos = 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){
            if(found){
                cout << "NOT UNIQUE\n";
                return 0;
            }
            else{
                found = true;
                pos = i;
            }
        }
    }
    if(found){
        if(pos >= upp){
            for(int i = 1;i<=upp-1;++i){
                cout << arr[i];
            }
            cout << "\n";
        }
        else{
            for(int i = 1;i<=pos-1;++i){
                cout << arr[i];
            }
            for(int i = pos+1;i<=upp;++i){
                cout << arr[i];
            }
            cout << "\n";
        }
    }
    else{
        cout << "NOT POSSIBLE\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...