Submission #930679

#	Time	Username	Problem	Language	Result	Execution time	Memory
930679		MinhAnhnd	Three Friends (BOI14_friends)	C++14	100 / 100	110 ms	37716 KiB

friends

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll __int128
#define maxn 300001
#define INF 1000000001
#define pa pair<ll,ll>
#define vi(t) vector<t>

//long long T[1000002];
long SS[2000002];
long Left[2000002];
long Right[2000002];
int main(){
    long N;

    cin>>N;
    for(long i = 1;i<=N;i++){
        char temp;
        cin>>temp;
        SS[i] = (long)temp;
    }
    if (N%2==0) {
        cout<<"NOT POSSIBLE";
        return 0;
    }
    long j = N/2 + 1;
    long used = 0;
    for (long i = 1;i<=N/2;i++){
        Left[i] = SS[i];
        while(SS[i]!=SS[j]){
            j++;
            used++;
            if (used==2){
                Left[0] = 1;
                break;
            }
        }
        if (used==2){
            Left[0] = 1;
            break;
        }
        j++;
    }
    //cout<<used;
    j = 1;
    used = 0;
    for (long i = 1;i<=N/2;i++){
        Right[i] = SS[i+N/2+1];
        while(SS[i+N/2+1]!=SS[j]){
            j++;
            used++;
            if (used==2){
                Right[0] = 2;
                break;
            }
        }
        if (used==2){
            Right[0] = 2;
            break;
        }
        j++;
    }

    if (Right[0]==2 && Left[0]==1){
        cout<<"NOT POSSIBLE";
        return 0 ;
    }
    if (Right[0]==2){
        for (long i = 1;i<=N/2;i++) cout<<(char)Left[i];
        return 0;
    }
    if (Left[0]==1){
        for (long i = 1;i<=N/2;i++) cout<<(char)Right[i];
        return 0;
    }
    for (long i = 1;i<=N/2;i++) if (Left[i]!=Right[i]){
        cout<<"NOT UNIQUE";
        return 0;
    }
    for (long i = 1;i<=N/2;i++) cout<<(char)Right[i];
}

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