Submission #535144

#	Time	Username	Problem	Language	Result	Execution time	Memory
535144		__Variatto	Three Friends (BOI14_friends)	C++17	100 / 100	118 ms	35184 KiB

friends

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=2e6+10, P=313, mod=1e9+696969;
int n;
ll hasz[MAX], pot[MAX];
string s;
ll fh(int a, int b){
    return ((hasz[b]-(hasz[a-1]*pot[b-a+1])%mod)+mod)%mod;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    pot[0]=1;
    for(int i=1; i<=MAX-5; i++)
        pot[i]=(pot[i-1]*P)%mod;
    cin>>n>>s;
    if(n%2==0){
        cout<<"NOT POSSIBLE\n";
        return 0;
    }
    s='%'+s;
    for(int i=1; i<=n; i++)
        hasz[i]=((hasz[i-1]*P)%mod+(s[i]-'A'))%mod;
    int ile=0, wyn=0;
    ll last=-1;
    for(int i=1; i<=n; i++){
        if(i==n/2+1 && fh(1, n/2)==fh(n/2+2, n)){
            if(last!=-1 && fh(n/2+2, n)!=last){
                cout<<"NOT UNIQUE\n";
                return 0;
            }
            ile++, wyn=i, last=fh(n/2+2, n);
        }
        if(i<n/2+1){
            ll l=fh(1, i-1), p=fh(i+1, n/2+1);
            ll caly=((l*pot[n/2+1-i-1+1])%mod+p)%mod;
            if(caly==fh(n/2+2, n)){
                if(last!=-1 && caly!=last){
                    cout<<"NOT UNIQUE\n";
                    return 0;
                }
                wyn=i, ile++, last=caly;
            }
        }
        if(i>n/2+1){
            ll l=fh(n/2+1, i-1), p=fh(i+1, n);
            ll caly=((l*pot[max(0, n-i-1+1)])%mod+p)%mod;
            if(caly==fh(1, n/2)){
                if(last!=-1 && caly!=last){
                    cout<<"NOT UNIQUE\n";
                    return 0;
                }
                wyn=i, ile++, last=caly;
            }
        }
    }
    if(!ile)
        cout<<"NOT POSSIBLE\n";        
    else{
        int xd=0;
        for(int i=1; i<=n; i++){
            if(i!=wyn){
                cout<<s[i];
                xd++;
            }
            if(xd==n/2)
                break;
        }
        cout<<"\n";
    }
}

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