제출 #889792

#제출 시각아이디문제언어결과실행 시간메모리
889792dwuy세 명의 친구들 (BOI14_friends)C++14
35 / 100
16 ms17496 KiB
/// dwuy: _,\,,,_\,__,\,,_ #include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout) #define fi first #define se second #define endl "\n" #define len(s) int32_t(s.length()) #define MASK(k)(1LL<<(k)) #define TASK "" #define int long long using namespace std; typedef tuple<int, int, int> tpiii; typedef pair<double, double> pdd; typedef pair<int, int> pii; typedef long long ll; const long long OO = 1e18; const int MOD1 = 998244353; const int MOD2 = 1e9 + 7; const int INF = 1e9; const int MX = 200005; const int base = 307; int n; int pf1[MX]; int pf2[MX]; int bp1[MX]; int bp2[MX]; string s; void nhap(){ cin >> n; cin >> s; if(!(n&1)){ cout << "NOT POSSIBLE"; exit(0); } } int add1(int a, int b){ a += b; return a + (a>=MOD1? -MOD1 : a<0? MOD1 : 0); } int mul1(int a, int b){ return a*b%MOD1; } int add2(int a, int b){ a += b; return a + (a>=MOD2? -MOD2 : a<0? MOD2 : 0); } int mul2(int a, int b){ return a*b%MOD2; } int get1(int l, int r){ return add1(pf1[r], -mul1(pf1[l-1], bp1[r-l+1])); } int get2(int l, int r){ return add2(pf2[r], -mul2(pf2[l-1], bp2[r-l+1])); } void solve(){ s = ' ' + s; bp1[0] = bp2[0] = 1; for(int i=1; i<=n; i++){ bp1[i] = mul1(bp1[i-1], base); bp2[i] = mul2(bp2[i-1], base); } for(int i=1; i<=n; i++){ pf1[i] = add1(mul1(pf1[i-1], base), s[i]); pf2[i] = add2(mul2(pf2[i-1], base), s[i]); } int flag = -1; int mid = (n+1)>>1; bool isUnique = 1; pii p = {-1, -1}; pii pre = {get1(1, mid-1), get2(1, mid-1)}; pii suf = {get1(mid+1, n), get2(mid+1, n)}; for(int i=1; i<=mid; i++){ int cur1 = add1(mul1(get1(1, i-1), bp1[mid-i]), get1(i+1, mid)); int cur2 = add2(mul2(get2(1, i-1), bp2[mid-i]), get2(i+1, mid)); pii cur = {cur1, cur2}; if(cur == suf){ flag = 0; if(p.fi < 0) p = cur; if(p != cur) isUnique = 0; } } for(int i=mid+1; i<=n; i++){ int cur1 = add1(mul1(get1(mid, i-1), bp1[n-i]), get1(i+1, n)); int cur2 = add2(mul2(get2(mid, i-1), bp2[n-i]), get2(i+1, n)); pii cur = {cur1, cur2}; if(cur == pre){ flag = 1; if(p.fi < 0) p = cur; if(p != cur) isUnique = 0; } } if(flag == -1) cout << "NOT POSSIBLE", exit(0); if(!isUnique) cout << "NOT UNIQUE", exit(0); if(!flag) for(int i=mid+1; i<=n; i++) cout << s[i]; else for(int i=1; i<mid; i++) cout << s[i]; } int32_t main(){ fastIO; //file(TASK); nhap(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...