Submission #85911

#	Time	Username	Problem	Language	Result	Execution time	Memory
85911		igzi	Three Friends (BOI14_friends)	C++17	0 / 100	29 ms	20512 KiB

friends

#include <bits/stdc++.h>
#define mod 1000000007
#define maxN 500005

using namespace std;

string s;
long long h[maxN],p[maxN],t,tmp,pom,n,i,ans;
vector <long long> v;

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin>>n;
    cin>>s;
    if(n%2==0) {cout<<"NOT POSSIBLE"<<endl; return 0;}
    h[0]=s[0]-'A'+1;
    p[0]=1;
    for(i=1;i<s.size();i++){p[i]=27*p[i-1]%mod; h[i]=h[i-1]+p[i]*(s[i]-'A'+1); h[i]=h[i]%mod;}
    t=(n-1)/2;
    for(i=0;i<n;i++){
        if(i<t){
            if(i>0) tmp=(p[t+1]*(h[i-1])+p[t]*(h[t]-h[i]))%mod;
            else tmp=p[t]*(h[t]-h[0])%mod;
            pom=(h[n-1]-h[t]+mod)%mod;
            if((tmp+mod)%mod==(pom+mod)%mod && (v.empty() || v[0]!=tmp)) {v.push_back(tmp); ans=i;}
        }
        else{
            if(i<n-1) tmp=(27*(h[i-1]-h[t-1])+(h[n-1]-h[i]))%mod;
            else tmp=27*(h[n-2]-h[t-1])%mod;
            pom=p[t+1]*h[t-1]%mod;
            if((tmp+mod)%mod==(pom+mod)%mod && (v.empty() || v[0]!=tmp)) {v.push_back(tmp); ans=i;}
        }
        if(v.size()>1) {cout<<"NOT UNIQUE"<<endl; return 0;}
    }
    if(v.size()==0) {cout<<"NOT POSSIBLE"<<endl; return 0;}
    for(i=0;i<t;i++){if(ans!=i) cout<<s[i];}
    if(ans<t) cout<<s[t];
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:19:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1;i<s.size();i++){p[i]=27*p[i-1]%mod; h[i]=h[i-1]+p[i]*(s[i]-'A'+1); h[i]=h[i]%mod;}
             ~^~~~~~~~~

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