Submission #107559

#TimeUsernameProblemLanguageResultExecution timeMemory
107559dfistricThree Friends (BOI14_friends)C++14
0 / 100
15 ms7816 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 = 200100; int ha[MAXN], pot[MAXN]; const int BASE = 35537, MOD = 1e9 + 7; int val(int x, int y) { if (y < x) return 0; int out = ha[y]; if (x) out -= ha[x - 1] * pot[y - x + 1]; return out; } int main() { ios_base::sync_with_stdio(false); pot[0] = 1; FOR(i, 1, MAXN) pot[i] = pot[i - 1] * BASE; int n; cin >> n; string s; cin >> s; int curr = 0; REP(i, n) { curr = curr * BASE + s[i]; ha[i] = curr; } string out = ""; REP(i, n) { if (i <= n / 2) { int a = val(0, i - 1) * pot[n / 2 - i] + val(i + 1, n / 2); int b = val(n / 2 + 1, n - 1); if (a != b) continue; string curr = s.substr(n / 2 + 1, n / 2); //cout << i << " " << curr << endl; if (out != "" && out != curr) { cout << "NOT UNIQUE\n"; return 0; } else { out = curr; } } else { int a = val(0, n / 2 - 1); int b = val(n / 2, i - 1) * pot[n - i - 1] + val(i + 1, n - 1); if (a != b) continue; string curr = s.substr(0, n / 2 - 1); //cout << i << " " << curr << endl; if (out != "" && out != curr) { cout << "NOT UNIQUE\n"; return 0; } else { out = curr; } } } if (out == "") cout << "NOT POSSIBLE\n"; else cout << out << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...