Submission #987281

#	Time	Username	Problem	Language	Result	Execution time	Memory
987281		Aiperiii	Three Friends (BOI14_friends)	C++14	35 / 100	1063 ms	37204 KiB

friends

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=2e6+5,t=33,mod=1e9+7;
int pw[N];
char s[N];
int cnt=0;
string ans="";
vector <int> p1,p2;
bool ok(int l1,int r1,int l2,int r2){
    if(l1>r1)return 1;
    int h1=(p1[r1]-(p1[l1-1]*pw[r1-l1+1]));
    if(h1<0)h1+=(abs(h1)/mod+1)*mod;
    h1%=mod;
    int h2=(p2[r2]-(p2[l2-1]*pw[r2-l2+1]));
    if(h2<0)h2+=(abs(h2)/mod+1)*mod;
    h2%=mod;
    if(h1==h2)return 1;
    return 0;
}
void calc(string x,string y){
    p1.clear();
    p2.clear();
    p1.pb(0);p2.pb(0);
    //cout<<x<<" "<<y<<"\n";
    for(int i=1;i<x.size();i++){
        p1.pb((p1[i-1]*t+x[i])%mod);
    }
    for(int i=1;i<y.size();i++){
        p2.pb((p2[i-1]*t+y[i])%mod);
    }
    bool tt=0;
    for(int i=1;i<x.size();i++){
        if(ok(1,i-1,1,i-1) && ok(i+1,x.size()-1,i,x.size()-2)){
            tt=1;
            ans=y;
        }
    }
    if(tt)cnt++;
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    if(n%2==0){
        cout<<"NOT POSSIBLE\n";
        return 0;
    }
    string x=" ",y=" ",a=" ",b=" ";
    for(int i=0;i<n;i++){
        if(i<=n/2)x+=s[i];
        else y+=s[i];
        if(i<n/2)a+=s[i];
        else b+=s[i];
    }
    pw[0]=1;
    for(int i=1;i<x.size();i++){
        pw[i]=pw[i-1]*t%mod;
    }
    calc(x,y);
    calc(b,a);
    if(!cnt)cout<<"NOT POSSIBLE\n";
    else if(cnt==1 or y==a){
        ans.erase(0,1);
        cout<<ans<<"\n";
    }
    else cout<<"NOT UNIQUE\n";
}

/*

*/

Compilation message (stderr)

friends.cpp: In function 'void calc(std::string, std::string)':
friends.cpp:30:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=1;i<x.size();i++){
      |                 ~^~~~~~~~~
friends.cpp:33:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=1;i<y.size();i++){
      |                 ~^~~~~~~~~
friends.cpp:37:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=1;i<x.size();i++){
      |                 ~^~~~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:65:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=1;i<x.size();i++){
      |                 ~^~~~~~~~~

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