제출 #31381

#제출 시각아이디문제언어결과실행 시간메모리
31381imaxblue세 명의 친구들 (BOI14_friends)C++14
100 / 100
146 ms23484 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define x first #define y second #define pii pair<int, int> #define p3i pair<pii, int> #define pll pair<ll, ll> #define p3l pair<pll, ll> #define lseg L, (L+R)/2, N*2+1 #define rseg (L+R)/2+1, R, N*2+2 #define ub upper_bound #define lb lower_bound #define pq priority_queue #define MN 1000000007 #define fox(k, x) for (int k=0; k<x; ++k) #define fox1(k, x) for (int k=1; k<=x; ++k) #define foxr(k, x) for (int k=x-1; k>=0; --k) #define fox1r(k, x) for (int k=x; k>0; --k) #define ms multiset #define flood(x) memset(x, 0x3f3f3f3f, sizeof x) #define drain(x) memset(x, 0, sizeof x) #define rng() (rand() >> 3)*rand() int n, c[2], p=-1, ans, seed=1337, k[2000005], hsh[2000005], hsh2; string s; int main(){ //cin.sync_with_stdio(0); //cin.tie(0); //cout.sync_with_stdio(0); //cout.tie(0); cin >> n >> s; n=s.size(); if (n%2==0){ cout << "NOT POSSIBLE"; return 0; } fox(l, n/2+1){ c[s[l]==s[l+n/2]]++; } k[n-1]=1; foxr(l, n){ hsh[l]=(hsh[l+1]+1LL*s[l]*k[l])%MN; if (l>0) k[l-1]=(1LL*k[l]*seed)%MN; //cout << hsh[l] << ' '; } //cout << endl; fox(l, n){ if (l<=n/2) c[s[l]==s[l+n/2]]--; else c[s[l]==s[l-n/2-1]]--; if (c[0]==0){ // cout << (1LL*hsh2+hsh[l+1])%MN << endl; if (p!=-1 && (1LL*hsh2+hsh[l+1])%MN!=ans){ cout << "NOT UNIQUE"; return 0; } p=l; ans=(1LL*hsh2+hsh[l+1])%MN; } hsh2=(hsh2+1LL*k[l+1]*s[l])%MN; //cout << c[0] << endl; if (l<n/2) c[s[l]==s[l+n/2+1]]++; else c[s[l]==s[l-n/2]]++; } if (p==-1) cout << "NOT POSSIBLE"; else { //if (p>=n) while(1); s.erase(p, 1); s.erase(0, n/2); cout << s; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...