Submission #1189662

#TimeUsernameProblemLanguageResultExecution timeMemory
1189662ArdelionThree Friends (BOI14_friends)C++20
0 / 100
6 ms5604 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("Ofast") //#pragma GCC optimize("O3") //#pragma GCC target("avx2") using namespace std; #define int long long #define ll long long #define X first #define Y second #define lc (id<<1) #define rc (lc|1) #define mid ((l+r+1)>>1) #define pb push_back #define lb lower_bound #define ub upper_bound #define mp make_pair #define sep ' ' #define endl "\n" #define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define FileIO freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #define all(x) x.begin(), x.end() #define ret(x) {cout << x << endl; return;} typedef pair<int, int> pii; typedef pair<ll , ll > pll; const int N = 2e5+13; const int LOG = 23; const int MOD = 1e9 + 7; //998244353; //1e9+9; const int BASE = 691; const int INF = 1e9; //1e18; const int dx[4] = {1, -1, 0, 0}; const int dy[4] = {0, 0, 1, -1}; ll md(ll x) {x%=MOD; return (x < 0 ? x+MOD : x);} ll GCD(ll _a, ll _b) { return (!_b ? _a : GCD(_b, _a % _b)); } ll POW(ll _a, ll _b) { return !_b ? 1 : ((_b & 1 ? _a : 1) * POW(_a * _a % MOD, _b / 2)) % MOD;} int n, invBASE; int p[N], ip[N], seg[N<<2], laz[N<<2]; string s; vector<int> ans; void update(int id, int x) { seg[id] = md(seg[id] * x); laz[id] = md(laz[id] * x); } void push(int id) { update(lc, laz[id]); update(rc, laz[id]); laz[id] = 1; } void build(int id, int l, int r) { laz[id] = 1; if(r-l == 1) { seg[id] = md(p[l] * s[l]); return; } build(lc, l, mid); build(rc, mid, r); seg[id] = md(seg[lc] + seg[rc]); } void upd(int id, int l, int r, int pos, int val) { if(r-l == 1) { seg[id] = md(val); return; } push(id); if(pos < mid) upd(lc, l, mid, pos, val); else upd(rc, mid, r, pos, val); seg[id] = md(seg[lc] + seg[rc]); } void mul(int id, int l, int r, int ql, int qr, int val) { if(r <= ql || qr <= l) return; if(ql <= l && r <= qr) { update(id, val); return; } push(id); mul(lc, l, mid, ql, qr, val); mul(rc, mid, r, ql, qr, val); seg[id] = md(seg[lc] + seg[rc]); } int get(int id, int l, int r, int ql, int qr) { if(r <= ql || qr <= l) return 0; if(ql <= l && r <= qr) return seg[id]; push(id); return md(get(lc, l, mid, ql, qr) + get(rc, mid, r, ql, qr)); } bool check(int i) { int x = get(1, 0, n, i, i+1); upd(1, 0, n, i, 0); mul(1, 0, n, i, n, ip[1]); int fh, sh, m; if(i < (n>>1)) { m = (n>>1)+1; } else { m = n>>1; } sh = get(1, 0, n, 0, m); fh = get(1, 0, n, m, n); fh = md(fh * ip[n>>1]); bool f = (fh == sh); // cout << m << sep << sh << sep << fh << sep; mul(1, 0, n, i, n, p[1]); upd(1, 0, n, i, x); return f; } void PREP() { p[0] = 1; for(int i = 1; i < N; i++) p[i] = md(p[i-1] * BASE); ip[N-1] = POW(p[N-1], MOD-2); for(int i = N-1; i > 0; i--) { ip[i-1] = md(ip[i] * BASE); } } void F() { cin >> n >> s; if(!(1&n)) ret("NOT POSSIBLE"); build(1, 0, n); for(int i = 0; i < n; i++) { if(check(i)) ans.pb(i); } if(ans.size() == 0) { ret("NOT POSSIBLE"); } if(ans.size() > 1) { ret("NOT UNIQUE"); } string t = ""; for(int i = 0; i < n; i++) { if(i != ans[0]) t.pb(s[i]); } while(t.size() > (n>>1)) t.pop_back(); ret(t); // cout << check(0); // cout << get(1, 0, n, 0, 3) << sep << md(get(1, 0, n, 4, 7) * ip[4]); // cout << md(ip[1] * BASE); } int32_t main() { migmig; PREP(); int t=1; //cin >> t; while(t--) F(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...