제출 #1182804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182804		_dtq_	세 명의 친구들 (BOI14_friends)	C++20	0 / 100	90 ms	68996 KiB

friends

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(x) (long long)(x.size())
using namespace std;

const ll N = 2e6 + 9;

const ll oo = 1e9 + 7;

const ll oo2 = 1e9 + 1;

const ll base = 311;

const ll base2 = 313;

ll n, i, has[N], poww[N], has2[N], poww2[N];

string s;

set<ll>ans;

ll get( ll l, ll r )
{
    if( l > r ) return 0;

    return (has[r] - has[l - 1] * poww[r - l + 1] % oo + oo * oo) % oo;
}

ll get2( ll l, ll r )
{
    if( l > r ) return 0;

    return (has2[r] - has2[l - 1] * poww2[r - l + 1] % oo2 + oo2 * oo2) % oo2;
}

int main()
{

    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> s;

    s = '0' + s;

    poww[0] = 1;

    poww2[0] = 1;

    for( i = 1; i < sz(s); i ++ )
    {
        has[i] = (has[i - 1] * base + (ll)(s[i])) % oo;

        poww[i] = poww[i - 1] * base % oo;

        has2[i] = (has2[i - 1] * base2 + (ll)(s[i])) % oo2;

        poww2[i] = poww2[i - 1] * base2 % oo2;
    }

    if(sz(s) & 1)
    {
        cout << "NOT IMPOSSIBLE";

        return 0;
    }

    string res = "";

    for( i = 1; i < sz(s); i ++ )
    {

        ll kc = sz(s) / 2 - 1;

        ll vt1 = kc;

        ll k1, k2, k3, k4;

        if(vt1 >= i)
        {
            vt1 ++;

            k1 = get(1, i - 1);

            k1 = k1 * poww[vt1 - i] + get(i + 1, vt1);

            k1 %= oo;

            k2 = get(vt1 + 1, sz(s) - 1);


            k3 = get2(1, i - 1);

            k3 = k3 * poww2[vt1 - i] + get2(i + 1, vt1);

            k3 %= oo2;

            k4 = get2(vt1 + 1, sz(s) - 1);
        }
        else
        {
            k1 = get(1, vt1);

            vt1 ++;

            k2 = get(vt1, i - 1);

            k2 = k2 * poww[sz(s) - 1 - i] + get(i + 1, sz(s) - 1);

            k2 %= oo;

            vt1 --;

            k3 = get2(1, vt1);

            vt1 ++;

            k4 = get2(vt1, i - 1);

            k4 = k4 * poww2[sz(s) - 1 - i] + get2(i + 1, sz(s) - 1);

            k4 %= oo2;
        }


        if(k1 != k2 || k3 != k4) continue;

        ans.insert(k1);

        if(res != "") continue;

        ll dem = 0;

        for( int w = 1; w < sz(s); w ++ )
        {
            if(dem == kc) break;

            if(w == i) continue;

            res += s[w];

            dem ++;
        }
    }

    if(sz(ans) == 0)
    {
        cout << "NOT IMPOSSIBLE";

        return 0;
    }

    if(sz(ans) != 1)
    {
        cout << "NOT UNIQUE";

        return 0;
    }

    cout << res;

    return 0;
}
/*
7
ABXCABC
*/

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