Submission #91886

#	Time	Username	Problem	Language	Result	Execution time	Memory
91886		karma	Three Friends (BOI14_friends)	C++11	100 / 100	129 ms	36692 KiB

friends

#include<bits/stdc++.h>
#define For(i, a, b)  for(int i = a, _b = b; i <= _b; ++i)
#define Ford(i, a, b) for(int i = a, _b = b; i >= _b; --i)
#define FileName      "test"
#define ll            long long
#define ld            long double
#define ull           unsigned long
#define Print(x)      cerr << #x << "is " << x << '\n';
#define pb            push_back
#define X             first
#define Y             second
//#define Karma

using namespace std;

template<typename T> inline void Cin(T &x)
{
    char c;
    T sign = 1;
    x = 0;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-') sign = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= sign;
}
template <typename T> inline void Out(T x) {if(x > 9) Out(x / 10); putchar(x % 10 + '0');}
template <typename T> inline void Cout(T x, char c) {if(x < 0) putchar('-'); x = abs(x); Out(x); putchar(c);}
template <typename T, typename... Args> inline void Cin(T& a, Args&... args) {Cin(a);Cin(args...);}
template <typename T, typename... Args> inline void Cout(T a, char c, Args... args) {Cout(a, c);Cout(args...);}

typedef pair<int, int> pii;
typedef pair<ll, int> plli;
const int N = 2e6 + 7;
const ll Base = 35;
const ll mod = 2147483647;

ll Hash[N], p[N], n, cnt, pos;
string s;
unordered_map<ll, bool> mmap;

ll GetHash(int l, int r)
{
    return (Hash[r] - Hash[l - 1] * p[r - l + 1] + mod * mod) % mod;
}

void Enter()
{
     cin >> n >> s;
     p[0] = 1;
     s = ' ' + s;
     For(i, 1, n + 3) p[i] = (p[i - 1] * Base) % mod;
     For(i, 1, n) Hash[i] = (Hash[i - 1] * Base + s[i] - 'A' + 1) % mod;
     if(n % 2 == 0) {cout << "NOT POSSIBLE"; exit(0);}
}

void Solve()
{
     if(GetHash(2, (n + 1) / 2) == GetHash((n + 3) / 2, n)) ++cnt, pos = 1, mmap[GetHash(2, n / 2 + 1)] = 1;
     if(GetHash(1, n / 2) == GetHash(n / 2 + 1, n - 1) && !mmap[GetHash(1, n / 2)]) ++cnt, pos = n, mmap[GetHash(1, n / 2)] = 1;
     if(GetHash(1, n / 2) == GetHash(n / 2 + 2, n) && !mmap[GetHash(1, n / 2)]) ++cnt, pos = n / 2 + 1, mmap[GetHash(1, n / 2)] = 1;
     For(i, 2, n - 1)
     {
         if(i < n / 2 + 1)
         {
            ll compare = GetHash(n / 2 + 2, n), st = GetHash(1, i - 1), len = n / 2 + 1 - i;
            if(mmap[compare]) continue;
            ll en = GetHash(i + 1, i + len);
            ll connect = ((st * p[len]) % mod + en) % mod;
            if(connect == compare) ++cnt, pos = i, mmap[compare] = 1;
         }
         else if(i > n / 2 + 1)
         {
            ll compare = GetHash(1, n / 2), st = GetHash(n / 2 + 1, i - 1), len = n - i;
            if(mmap[compare]) continue;
            ll en = GetHash(n - len + 1, n);
            ll connect = (st * p[len] % mod) + en;
            connect %= mod;
            if(connect == compare) ++cnt, pos = i, mmap[compare] = 1;
         }
     }
     if(cnt > 1) cout << "NOT UNIQUE";
     else if(cnt == 0) cout << "NOT POSSIBLE";
     else
     {
         if(pos >= n / 2 + 1) For(i, 1, n / 2) cout << s[i];
         else For(i, n / 2 + 2, n) cout << s[i];
     }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#ifdef Karma
    freopen(FileName".inp", "r", stdin);
    freopen(FileName".out", "w", stdout);
#endif // Karma

    Enter();
    Solve();

    return 0;
}

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