제출 #889773

#제출 시각아이디문제언어결과실행 시간메모리
889773dwuy세 명의 친구들 (BOI14_friends)C++14
0 / 100
17 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 cnt = 0; int flag = -1; int mid = (n+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) cnt++, flag = 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) cnt++, flag = 1; } if(cnt == 0) cout << "NOT POSSIBLE", exit(0); if(cnt > 1) 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...