Submission #1160006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160006		Ludissey	세 명의 친구들 (BOI14_friends)	C++20	35 / 100	524 ms	52056 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=31;
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=(cp*hashP)%MOD;
        j++;
    }
    int mid=((n-1)/2)-1;
    int ans=-1;
    unordered_set<int> st;
    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])%MOD;
            lft=(getHASH(0,i-1)+(getHASH(i+1,mid+1)*fppow[1])%MOD)%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) {
            st.insert(lft%MOD);
            ans=i;
        }
    }
    if(ans==-1) cout << "NOT POSSIBLE\n";
    else if(sz(st)>1) cout << "NOT UNIQUE\n";
    else{
        int j=n/2;
        int k=0;
        string str="";
        for (int i = 0; i < n; i++)
        {
            if(i==ans) continue;
            str+=s[i];
            k++;
            if(k==j) break;
        }
        
        cout << str <<"\n";
    }
    return 0;
}

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