This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
//const int mod = 1000000007;
//Note to self: Check for overflow
int power(int a, int n, int mod)
{
li c=1;
while (n)
{
if (n&1) (c*=a)%=mod;
a=(li)a*a%mod,n>>=1;
}
return c;
}
mt19937 rng(2942023);
char s[2000005];
int w[256];
const int H=2;
struct hesiranje
{
int pre[2000005];
int p,mod;
int pw[2000005];
int iw[2000005];
void setprost(int _p)
{
p=_p;
}
void setmod(int _mod)
{
mod=_mod;
}
void build(int n)
{
ff(i,0,256) w[i]=rng()%mod;
pw[0]=1;
fff(i,1,n) pw[i]=(li)pw[i-1]*p%mod;
iw[0]=1;
iw[1]=power(p,mod-2,mod);
fff(i,2,n) iw[i]=(li)iw[i-1]*iw[1]%mod;
fff(i,1,n) pre[i]=((li)pre[i-1]*p+w[s[i]])%mod;
}
int Hash(int ll, int rr)
{
return (pre[rr]+mod-(li)pre[ll-1]*pw[rr-ll+1]%mod)%mod;
}
int ComboHash(int l1, int r1, int l2, int r2)
{
return (Hash(l2,r2)+(li)pw[r2-l2+1]*Hash(l1,r1)%mod)%mod;
}
} hes[H];
vector<int> brisem; //ako ih ima vise, ispisati not unique; ako ih nema uopste, ispisati not possible
int main()
{
FAST;
int n; cin>>n;
fff(i,1,n) cin>>s[i];
if (!(n&1)) return cout<<"NOT POSSIBLE",0;
hes[0].setprost(143);
hes[0].setmod(998244353);
hes[1].setprost(1000003);
hes[1].setmod(998244353);
/*hes[2].setprost(143);
hes[2].setmod(1000000007);
hes[3].setprost(1000003);
hes[3].setmod(1000000007);
hes[4].setprost(143);
hes[4].setmod(1000000009);
hes[5].setprost(1000003);
hes[5].setmod(1000000009);*/
ff(koji,0,H) hes[koji].build(n);
fff(i,1,(n+1)/2)
{
bool jednaki=true;
ff(koji,0,H) if (hes[koji].ComboHash(1,i-1,i+1,(n+1)/2) != hes[koji].Hash((n+1)/2+1,n)) jednaki=false;
if (jednaki) brisem.pb(i);
}
fff(i,(n+1)/2+1,n)
{
bool jednaki=true;
ff(koji,0,H) if (hes[koji].Hash(1,(n+1)/2-1) != hes[koji].ComboHash((n+1)/2,i-1,i+1,n)) jednaki=false;
if (jednaki) brisem.pb(i);
}
if (brisem.empty()) return cout<<"NOT POSSIBLE",0;
if ((int)brisem.size()>1) return cout<<"NOT UNIQUE",0;
s[brisem[0]]=0;
string ans;
fff(i,1,n)
{
if (s[i]) ans.pb(s[i]);
if ((int)ans.size()==n/2) break;
}
cout<<ans<<"\n";
}
//Note to self: Check for overflow
Compilation message (stderr)
friends.cpp: In member function 'void hesiranje::build(int)':
friends.cpp:82:48: warning: array subscript has type 'char' [-Wchar-subscripts]
82 | fff(i,1,n) pre[i]=((li)pre[i-1]*p+w[s[i]])%mod;
| ~~~^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |