Submission #151390

#	Time	Username	Problem	Language	Result	Execution time	Memory
151390		Kamisama	Three Friends (BOI14_friends)	C++14	0 / 100	100 ms	19160 KiB

friends

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <chrono>
#include <unordered_map>
#define Kami
#define taskname "TEST"
using namespace std;
const int maxn=2e6+7;
const int mod=1e9+7;
const int base=227;

int n,res,deletedPos;
int p[maxn],h[maxn];
string s;
unordered_map<int,bool> exist;

inline void Input(){
    cin>>n>>s;
    s=' '+s;
}

inline void Init(){
    p[0]=1;
    for(int i=1;i<=n;i++) p[i]=1ll*p[i-1]*base%mod;
    for(int i=1;i<=n;i++) h[i]=(1ll*h[i-1]*base+s[i])%mod;
}

inline int GetHash(const int &i, const int &j){
    return (h[j]-1ll*h[i-1]*p[j-i+1]+1ll*mod*mod)%mod;
}

inline int Remove(const int &i, const int &j, const int &x){
    int head=GetHash(i,x-1);
    int tail=GetHash(x+1,j);
    return (1ll*head*p[j-x]+tail)%mod;
}

inline void Solve(){
    if(n%2==0) cout<<"NOT POSSIBLE",exit(0);
    int hashCode=GetHash(2,n/2+1); // remove the first character.
    if(hashCode==GetHash(n/2+2,n)){
        res++; deletedPos=1;
        exist[hashCode]=true;
    }
    hashCode=GetHash(1,n/2); // remove the last character.
    if(hashCode==GetHash(n/2+1,n-1) && !exist[hashCode]){
        res++; deletedPos=n;
        exist[GetHash(1,n/2)]=true;
    }
    for(int i=2;i<n;i++){ //remove characters in [2,n)
        if(i<=n/2){
            hashCode=Remove(1,n/2+1,i);
            if(hashCode==GetHash(n/2+2,n) && !exist[hashCode]){
                res++; deletedPos=i;
                exist[hashCode]=true;
            }
        } else{
            hashCode=Remove(n/2+1,n,i);
            if(hashCode==GetHash(1,n/2) && !exist[hashCode]){
                res++; deletedPos=i;
                exist[hashCode]=true;
            }
        }
    }
}

inline void PrintRes(){
    if(res==0) cout<<"NOT POSSIBLE";
    else if(res>1) cout<<"NOT UNIQUE";
    else{
        if(deletedPos<=n/2) for(int i=n/2+2;i<=n;i++) cout<<s[i];
        else for(int i=1;i<=n/2;i++) cout<<s[i];
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL); if(fopen(taskname".INP","r"))
    freopen(taskname".INP","r",stdin),
    freopen(taskname".OUT","w",stdout);
    #ifdef Kami
    auto start=chrono::steady_clock::now();
    #endif

    Input();
    Init();
    Solve();
    PrintRes();

    #ifdef Kami
    auto end=chrono::steady_clock::now();
    cerr<<"\nIn milliseconds : "
        <<chrono::duration_cast<chrono::milliseconds>(end-start).count();
    cerr<<'\n'<<"In seconds : "<<fixed<<setprecision(3)
        <<(double)chrono::duration_cast<chrono::milliseconds>(end-start).count()/1000<<'\n';
    #endif

    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:80:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(taskname".INP","r",stdin),
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
     freopen(taskname".OUT","w",stdout);
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
friends.cpp:80:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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