제출 #845115

#제출 시각아이디문제언어결과실행 시간메모리
845115vuavisao세 명의 친구들 (BOI14_friends)C++17
0 / 100
131 ms35768 KiB
#include<bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define ll long long using namespace std; const int N = 2e6 + 10; const uint8_t size_T = 2; const int _1hrd = 100; const int _1bil = 1000000000; const array<int, size_T> MOD = {_1bil + 9, _1bil + 11}; const array<int, size_T> BASE = {_1hrd + 28, _1hrd + 31}; struct Hash { array<int, size_T> val = {0}; Hash() {}; Hash (int x) { for (uint8_t i = 0; i < size_T; ++ i) this -> val[i] = x % MOD[i]; } bool operator < (const Hash& other) const { for (uint8_t i = 0; i < size_T; ++ i) if (this -> val[i] != other.val[i]) return this -> val[i] < other.val[i]; return false; } bool operator == (const Hash& other) const { for (uint8_t i = 0; i < size_T; ++ i) if (this -> val[i] != other.val[i]) return false; return true; } Hash operator + (const int& x) const { Hash res; for (uint8_t i = 0; i < size_T; ++ i) res.val[i] = (1ll * this -> val[i] * BASE[i] + x) % MOD[i]; return res; } Hash operator + (const Hash& other) const { Hash res; for (uint8_t i = 0; i < size_T; ++ i) { // res.val[i] = (this -> val[i] + other.val[i]) % MOD[i]; res.val[i] = (this -> val[i] + other.val[i]); res.val[i] = res.val[i] + (res.val[i] < 0) * MOD[i] - (res.val[i] >= MOD[i]) * MOD[i]; } return res; } Hash operator - (const Hash& other) const { Hash res; for (uint8_t i = 0; i < size_T; ++ i) { // res.val[i] = (this -> val[i] - other.val[i]) % MOD[i]; // res.val[i] = (res.val[i] + MOD[i]) % MOD[i]; res.val[i] = (this -> val[i] - other.val[i]); res.val[i] = res.val[i] + (res.val[i] < 0) * MOD[i] - (res.val[i] >= MOD[i]) * MOD[i]; } return res; } Hash operator * (const Hash& other) const { Hash res; for (uint8_t i = 0; i < size_T; ++ i) res.val[i] = (1ll * this -> val[i] * other.val[i]) % MOD[i]; return res; } friend ostream& operator << (ostream& os, Hash& other) { os << "[ "; for (uint8_t i = 0; i < size_T; ++ i) { os << other.val[i]; if(i < size_T - 1) os << ','; os << ' '; } os << "]"; return os; } }; int n; string s; Hash p[N], h[N]; Hash get_hash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); p[0] = 1; for(int i = 1; i <= 2000001; ++ i) p[i] = p[i - 1] + 0; cin >> n >> s; s = ' ' + s; for(int i = 1; i <= n; ++ i) h[i] = h[i - 1] + s[i]; if(!(n & 1)) { cout << "NOT POSSIBLE"; return 0; } int cnt_can_dif = 0, idx_dif = - 1; int len = n / 2; for(int i = 1; i <= n; ++ i) { if(i <= len) { int bonus = len - (i - 1); if(get_hash(1, i - 1) * p[bonus] + get_hash(i + 1, i + 1 + bonus - 1) == get_hash(i + 1 + bonus, n)) { ++ cnt_can_dif; idx_dif = i; } } else if(i > len + 1) { if(get_hash(1, len) == get_hash(len + 1, i - 1) * p[n - (i + 1) + 1] + get_hash(i + 1, n)) { ++ cnt_can_dif; idx_dif = i; } } else { if(get_hash(1, len) == get_hash(len + 2, n)) { ++ cnt_can_dif; idx_dif = i; } } } // cerr << cnt_can_dif << '\n'; if(cnt_can_dif == 0) { cout << "NOT POSSIBLE"; } else if(cnt_can_dif > 1) { cout << "NOT UNIQUE"; } else { for(int i = 1; len > 0; ++ i) { if(i == idx_dif) continue; -- len; cout << s[i]; } } return (0 ^ 0); } /// Code by vuavisao
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...