Submission #884506

#	Time	Username	Problem	Language	Result	Execution time	Memory
884506		12345678	Three Friends (BOI14_friends)	C++17	100 / 100	71 ms	30700 KiB

friends

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e6+5, mod=1e9+7;
ll n, sz, dp[nx], dp2[nx], p[nx], val, val2, ans1=-1, ans2=-1;
string s1, s2;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>s1;
    p[0]=1;
    for (int i=1; i<nx; i++) p[i]=(p[i-1]*26)%mod;
    sz=n/2;
    if (n%2==0)
    {
        cout<<"NOT POSSIBLE";
        return 0;
    }
    s2.resize(n);
    for (int i=0; i<sz+1; i++) s2[i]=s1[i+sz];
    for (int i=sz+1; i<n; i++) s2[i]=s1[i-sz-1];
    for (int i=sz+1; i<n; i++) val=(val+(s1[i]-'A')*p[i-sz-1])%mod;
    for (int i=1; i<=sz+1; i++) dp[i]=(dp[i-1]+(s1[i-1]-'A')*p[i-1])%mod;
    for (int i=sz+1; i>=1; i--) dp2[i]=(dp2[i+1]+(s1[i-1]-'A')*p[i-2])%mod;
    for (int i=0; i<=sz; i++) if ((dp[i]+dp2[i+2])%mod==val) ans1=i;
    for (int i=sz+1; i<n; i++) val2=(val2+(s2[i]-'A')*p[i-sz-1])%mod;
    for (int i=1; i<=sz+1; i++) dp[i]=(dp[i-1]+(s2[i-1]-'A')*p[i-1])%mod;
    for (int i=sz+1; i>=1; i--) dp2[i]=(dp2[i+1]+(s2[i-1]-'A')*p[i-2])%mod;
    for (int i=1; i<=sz; i++) if ((dp[i]+dp2[i+2])%mod==val2) ans2=i;
    if (ans1==-1&&ans2==-1)
    {
        cout<<"NOT POSSIBLE";
        return 0;
    }
    if (ans1!=-1&&ans2==-1)
    {
        for (int i=sz+1; i<n; i++) cout<<s1[i];
        return 0;
    }
    if (ans1==-1&&ans2!=-1)
    {
        for (int i=sz+1; i<n; i++) cout<<s2[i];
        return 0;
    }
    if (ans1!=-1&&ans2!=-1&&val==val2)
    {
        for (int i=sz+1; i<n; i++) cout<<s2[i];
        return 0;
    }
    cout<<"NOT UNIQUE";
}

/*
7
ABCAXBC
*/

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