Submission #1160001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160001		Ludissey	Three Friends (BOI14_friends)	C++20	0 / 100	508 ms	49452 KiB

friends

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

vector<int> hsh;
vector<int> ppow;
vector<int> fppow;

int hashP=58;
const int MOD=1e9+7;

int fast_pow(int x, int p){
    if(p==0) return 1;
    if(p==1) return x;
    if(p%2==0){
        int r=fast_pow(x,p/2);
        return (r*r)%MOD;
    }else{
        int r=fast_pow(x,p-1);
        return (r*x)%MOD;
    }
}

int getHASH(int i, int j){
    if(i>j) return 0;
    int ret=hsh[j];
    if(i>0) ret=(hsh[j]+MOD-hsh[i-1])%MOD;
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    ppow.resize(n);
    fppow.resize(n);
    hsh.resize(n);
    string s; cin >> s;
    if(n%2==0) {
        cout << "NOT POSSIBLE\n";
        return 0;
    }
    int cp=1;
    int j=0;
    for (auto u : s)
    {
        hsh[j]=(((int)u-'A')*cp)%MOD;
        if(j>0) hsh[j]=(hsh[j]+hsh[j-1])%MOD;
        ppow[j]=cp;
        fppow[j]=fast_pow(cp,MOD-2);
        cp*=hashP;
        j++;
    }
    int mid=((n-1)/2)-1;
    int ans=-1;
    for (int i = 0; i < n; i++)
    {
        int lft=0;
        int rgt=0;
        if(i<=mid) {
            rgt=(getHASH(mid+2,n-1)*fppow[mid+2]);
            lft=(getHASH(0,i-1)+(getHASH(i+1,mid+1)*fppow[1])%MOD);
        }else{
            rgt=(getHASH(mid+1,i-1)+(getHASH(i+1,n-1)*fppow[1]%MOD)*fppow[mid+1])%MOD;
            lft=getHASH(0,mid);
        }
        if(lft%MOD==rgt%MOD) {
            if(ans!=-1) ans=1e9;
            else ans=i;
        }
    }
    if(ans==-1) cout << "NOT POSSIBLE\n";
    else if(ans==1e9) cout << "NOT UNIQUE\n";
    else{
        int j=n/2+1;
        int k=0;
        while(j--){
            if(k==ans) {
                k++;
                continue;
            }
            cout << s[k];
            k++;
        }
        cout << "\n";
    }
    return 0;
}

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