Submission #107576

#TimeUsernameProblemLanguageResultExecution timeMemory
107576dfistricThree Friends (BOI14_friends)C++14
35 / 100
1085 ms70248 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define FORd(i, a, b) for (int i = (a); i >= (b); i--) #define REP(i, n) FOR(i, 0, n) #define ll long long using namespace std; const int MAXN = 2001000; ll ha[MAXN], pot[MAXN]; ll ha2[MAXN], pot2[MAXN]; const int BASE = 35537; const int MOD = 1e9 + 7; const int BASE2 = 57737; const int MOD2 = 1e9 + 9; ll val(int x, int y) { if (y < x) return 0; ll out = ha[y]; if (x) out = (((out - ha[x - 1] * pot[y - x + 1]) % MOD) + MOD) % MOD; return out; } ll val2(int x, int y) { if (y < x) return 0; ll out = ha2[y]; if (x) out = (((out - ha2[x - 1] * pot2[y - x + 1]) % MOD2) + MOD2) % MOD2; return out; } int main() { ios_base::sync_with_stdio(false); pot[0] = 1; FOR(i, 1, MAXN) pot[i] = (pot[i - 1] * BASE) % MOD; pot2[0] = 1; FOR(i, 1, MAXN) pot2[i] = (pot2[i - 1] * BASE2) % MOD2; int n; cin >> n; string s; cin >> s; if (n % 2 == 0) { cout << "NOT POSSIBLE\n"; return 0; } ll curr = 0, curr2 = 0; REP(i, n) { curr = (curr * BASE + s[i]) % MOD; ha[i] = curr; curr2 = (curr2 * BASE2 + s[i]) % MOD2; ha2[i] = curr2; } string out = ""; ll V = -1, V2 = -1; REP(i, n) { if (i <= n / 2) { ll a = (val(0, i - 1) * pot[n / 2 - i] + val(i + 1, n / 2)) % MOD; ll b = val(n / 2 + 1, n - 1); ll a2 = (val2(0, i - 1) * pot2[n / 2 - i] + val2(i + 1, n / 2)) % MOD2; ll b2 = val2(n / 2 + 1, n - 1); if (a != b) continue; if (a2 != b2) continue; string s1 = "", s2 = ""; REP(x, i) s1 += s[x]; FOR(x, i + 1, n / 2 + 1) s1 += s[x]; FOR(x, n / 2 + 1, n) s2 += s[x]; assert(s1 == s2); if (out != "" && (V != a || V2 != a2)) { cout << "NOT UNIQUE\n"; return 0; } else if (out == "") { V = a; V2 = a2; out = s.substr(n / 2 + 1, n / 2); } } else { ll a = val(0, n / 2 - 1); ll b = (val(n / 2, i - 1) * pot[n - i - 1] + val(i + 1, n - 1)) % MOD; ll a2 = val2(0, n / 2 - 1); ll b2 = (val2(n / 2, i - 1) * pot2[n - i - 1] + val2(i + 1, n - 1)) % MOD2; if (a != b) continue; if (a2 != b2) continue; string s1 = "", s2 = ""; REP(x, n / 2) s1 += s[x]; FOR(x, n / 2, i) s2 += s[x]; FOR(x, i + 1, n) s2 += s[x]; assert(s1 == s2); if (out != "" && (V != a || V2 != a2)) { cout << "NOT UNIQUE\n"; return 0; } else if (out == "") { V = a; V2 = a2; out = s.substr(0, n / 2); } } } if (out == "") cout << "NOT POSSIBLE\n"; else cout << out << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...