Submission #1066633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066633		giaminh2211	Three Friends (BOI14_friends)	C++14	0 / 100	76 ms	35844 KiB

friends

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int n;
const int base=37;
const int mod=1e9+7;
const int N=2e6+13;
ll f[N];
string a;
ll lt[N];
vector<int> v;

ll gethash(int l, int r){
    ll val=f[r]-f[l-1]*lt[r-l+1];
    val %= mod;
    while(val < 0) val += mod;
    return val;
}

ll getcon(int l, int r, int x, int y){
    ll val=gethash(l, r) * lt[y-x+1];
    val %= mod;
    val += gethash(x, y);
    val %= mod;
    return val;
}

void scan(){
    cin >> n >> a;
    if(n%2==0){
        cout << "NOT POSSIBLE";
        exit(0);
    }
    a=' '+a;
    lt[0]=1;
    for(int i=1; i<=n; i++){
        lt[i]=lt[i-1]*base%mod;
        f[i]=f[i-1] * base + (a[i]-'A'+1);
        f[i]%=mod;
    }
}

void solve(){
    for(int i=1; i<=n/2; i++){
        if(getcon(1, i-1, i+1, n/2+1)==gethash(n/2+2, n)){
            v.push_back(i);
        }
    }
    if(gethash(1, n/2)==gethash(n/2+2, n)){
        v.push_back(n/2+1);
    }
    for(int i=n/2+2; i<=n; i++){
        if(gethash(1, n/2)==getcon(n/2+1, i-1, i+1, n)){
            v.push_back(i);
        }
    }
    if(v.size()==0) cout << "NOT POSSIBLE";
    else if(v.size()==1){
        int id=v[0];
        for(int i=1; i<id; i++) cout << a[i];
        for(int i=id+1; i<=n; i++) cout << a[i];
    }
    else cout << "NOT UNIQUE";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    solve();
}

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