oj.uz

Submission #151390

# Submission time Handle Problem Language Result Execution time Memory
151390 2019-09-02T15:44:50 Z Kamisama Three Friends (BOI14_friends) C++14
0 / 100
 100 ms 19160 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 19160 KB Output isn't correct
2 Halted 0 ms 0 KB -