제출 #1351462

#제출 시각아이디문제언어결과실행 시간메모리
1351462Warinchai세 명의 친구들 (BOI14_friends)C++20
0 / 100
51 ms37560 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

int sum[2000005];
int pw[2000005];
int md=1e9+7;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    string s;cin>>s;
    if(n%2==0){
        cout<<"NOT POSSIBLE";
        return 0;
    }
    pw[0]=1;
    for(int i=1;i<=n;i++){
        int x=s[i-1]-'A';
        sum[i]=(sum[i-1]*26+x)%md;
        pw[i]=(pw[i-1]*26)%md;
        //cerr<<sum[i]<<" ";
    }
    //cerr<<"\n";
    int cnt=0,val=0;
    for(int i=1;i<=n;i++){
        int l=0,r=0;
        int m=n/2+1;
        //cerr<<"i:"<<i<<"\n";
        if(i<=m){
            l=(sum[i-1]*pw[m-i]+(sum[m]-sum[i]*pw[m-i])%md+md)%md;
            r=((sum[n]-sum[m]*pw[n-m])%md+md)%md;
            //cerr<<"r:"<<r<<"\n";
            if(l==r)cnt++,val=i;
            //cerr<<l<<" "<<r<<"\n";
        }else{
            l=sum[m-1];
            r=((sum[i-1]-sum[m-1]*(pw[i-m]))%md+md)%md;
            //cerr<<"r:"<<r<<"\n";
            r=(r*(pw[n-i]))%md;
            r+=(sum[n]-sum[i]*(pw[n-i]))%md+md;
            r%=md;
            if(l==r)cnt++,val=i;
            //cerr<<l<<" "<<r<<"\n";
        }
    }
    if(cnt==0){
        cout<<"NOT POSSIBLE";
    }
    else if(cnt>1){
        cout<<"NOT UNIQUE\n";
    }else{
        int cur=0;
        string ans;
        int cnt=0;
        for(int i=0;i<n;i++){
            if(i+1==val)continue;
            cnt++;
            ans.push_back(s[i]);
            if(cnt==n/2)break;
        }
        cout<<ans<<"\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...