Submission #137962

#	Time	Username	Problem	Language	Result	Execution time	Memory
137962		igzi	Three Friends (BOI14_friends)	C++17	35 / 100	29 ms	22424 KiB

friends

#include <bits/stdc++.h>
#define maxN 500005
 
using namespace std;
 
string s;
long long h[maxN],p[maxN],t,tmp,pom,n,i,ans;
vector <long long> v;
 
void prepare(){
h[0]=s[0]-'A'+1;
p[0]=1;
for(int i=1;i<s.size();i++){p[i]=27*p[i-1]; h[i]=h[i-1]+p[i]*(s[i]-'A'+1);}
}
 
int main()
{
    std::ios_base::sync_with_stdio(false);
    cin>>n;
    cin>>s;
    if(n%2==0) {cout<<"NOT POSSIBLE"<<endl; return 0;}
    prepare();
    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]);
            else tmp=p[t]*(h[t]-h[0]);
            pom=h[n-1]-h[t];
            if(tmp==pom && (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]);
            else tmp=27*(h[n-2]-h[t-1]);
            pom=p[t+1]*h[t-1];
            if(tmp==pom && (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 'void prepare()':
friends.cpp:13:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=1;i<s.size();i++){p[i]=27*p[i-1]; h[i]=h[i-1]+p[i]*(s[i]-'A'+1);}
             ~^~~~~~~~~

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