제출 #1182851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182851		_dtq_	Three Friends (BOI14_friends)	C++20	100 / 100	51 ms	37592 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 base = 311;

ll n, i, has[N], poww[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;
}

int main()
{

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

    cin >> n >> s;

    s = '0' + s;

    poww[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;
    }

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

        return 0;
    }

    string res = "";

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

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

        ll vt1 = kc;

        ll k1 = 0, k2 = 0;

        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);
        }
        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;
        }


        if(k1 != k2) 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 POSSIBLE";

        return 0;
    }

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

        return 0;
    }

    cout << res;

    return 0;
}
/*
7
ABXCABC
*/

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