/*
بسم الله الرحمن الرحيم
Author:
(:Muhammad Aneeq:)
*/
#include <iostream>
#include <set>
using namespace std;
#define int long long
int const base=997,mod=1e9+7,N=2000011;
int pw[N]={};
int power(int x,int y)
{
return pw[y];
}
inline void solve()
{
int n;
cin>>n;
string x;
cin>>x;
if (n%2==0)
{
cout<<"NOT POSSIBLE\n";return;
}
int hash[n+1]={};
int sz=n/2;
set<int>ans;
int ind=0;
for (int i=0;i<n;i++)
hash[i+1]=(hash[i]*base+x[i]-'A'+1)%mod;
for (int i=1;i<=(n+1)/2;i++)
{
int z=hash[i-1];
int f=sz-i+1;
int g=((hash[i+f]-(hash[i]*power(base,f))%mod)+mod)%mod;
z=(z*power(base,f)+g)%mod;
int y=((hash[n]-(hash[i+f]*power(base,sz))%mod)+mod)%mod;
if (z==y)
{
if (ans.find(z)==ans.end())
ind=i;
ans.insert(z);
if (ans.size()>1)
{
cout<<"NOT UNIQUE\n";return;
}
}
}
for (int i=(n+1)/2;i<=n;i++)
{
int z=hash[sz];
int y=((hash[i-1]-(hash[sz]*power(base,(i-1-sz)))%mod)+mod)%mod;
int u=((hash[n]-(hash[i]*power(base,(n-i)))%mod)+mod)%mod;
y=(y*power(base,(n-i))+u)%mod;
if (y==z)
{
if (ans.find(z)==ans.end())
ind=i;
ans.insert(z);
if (ans.size()>1)
{
cout<<"NOT UNIQUE\n";return;
}
}
}
if (ind==0)
{
cout<<"NOT POSSIBLE\n";return;
}
string g;
int i=1;
while (g.size()!=sz)
{
if (i==ind)
i++;
else
{
g+=x[i-1];i++;
}
}
cout<<g<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
pw[0]=1;
for (int i=1;i<N;i++)
pw[i]=(pw[i-1]*base)%mod;
solve();
}
Compilation message
friends.cpp: In function 'void solve()':
friends.cpp:74:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
74 | while (g.size()!=sz)
| ~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
16216 KB |
Output is correct |
2 |
Correct |
12 ms |
15964 KB |
Output is correct |
3 |
Correct |
11 ms |
16256 KB |
Output is correct |
4 |
Correct |
11 ms |
15964 KB |
Output is correct |
5 |
Correct |
11 ms |
15964 KB |
Output is correct |
6 |
Correct |
12 ms |
15964 KB |
Output is correct |
7 |
Correct |
11 ms |
15964 KB |
Output is correct |
8 |
Correct |
11 ms |
16008 KB |
Output is correct |
9 |
Correct |
11 ms |
15964 KB |
Output is correct |
10 |
Correct |
11 ms |
15964 KB |
Output is correct |
11 |
Correct |
11 ms |
15964 KB |
Output is correct |
12 |
Correct |
12 ms |
15960 KB |
Output is correct |
13 |
Correct |
11 ms |
15960 KB |
Output is correct |
14 |
Correct |
11 ms |
15964 KB |
Output is correct |
15 |
Correct |
11 ms |
16016 KB |
Output is correct |
16 |
Correct |
11 ms |
15964 KB |
Output is correct |
17 |
Correct |
11 ms |
15992 KB |
Output is correct |
18 |
Correct |
11 ms |
15964 KB |
Output is correct |
19 |
Correct |
11 ms |
15964 KB |
Output is correct |
20 |
Correct |
11 ms |
15964 KB |
Output is correct |
21 |
Correct |
11 ms |
16216 KB |
Output is correct |
22 |
Correct |
11 ms |
15960 KB |
Output is correct |
23 |
Correct |
11 ms |
15964 KB |
Output is correct |
24 |
Correct |
11 ms |
15992 KB |
Output is correct |
25 |
Correct |
11 ms |
15964 KB |
Output is correct |
26 |
Correct |
11 ms |
15988 KB |
Output is correct |
27 |
Correct |
11 ms |
15964 KB |
Output is correct |
28 |
Correct |
11 ms |
15960 KB |
Output is correct |
29 |
Correct |
11 ms |
15964 KB |
Output is correct |
30 |
Correct |
11 ms |
15964 KB |
Output is correct |
31 |
Correct |
11 ms |
15964 KB |
Output is correct |
32 |
Correct |
11 ms |
16004 KB |
Output is correct |
33 |
Correct |
12 ms |
15964 KB |
Output is correct |
34 |
Correct |
11 ms |
15964 KB |
Output is correct |
35 |
Correct |
11 ms |
15964 KB |
Output is correct |
36 |
Correct |
11 ms |
15960 KB |
Output is correct |
37 |
Correct |
11 ms |
16000 KB |
Output is correct |
38 |
Correct |
12 ms |
15964 KB |
Output is correct |
39 |
Correct |
11 ms |
15964 KB |
Output is correct |
40 |
Correct |
11 ms |
15964 KB |
Output is correct |
41 |
Correct |
11 ms |
15964 KB |
Output is correct |
42 |
Correct |
11 ms |
16216 KB |
Output is correct |
43 |
Correct |
11 ms |
16012 KB |
Output is correct |
44 |
Correct |
11 ms |
15996 KB |
Output is correct |
45 |
Correct |
11 ms |
15960 KB |
Output is correct |
46 |
Correct |
12 ms |
16216 KB |
Output is correct |
47 |
Correct |
11 ms |
15964 KB |
Output is correct |
48 |
Correct |
11 ms |
16004 KB |
Output is correct |
49 |
Correct |
11 ms |
15960 KB |
Output is correct |
50 |
Correct |
11 ms |
15964 KB |
Output is correct |
51 |
Correct |
11 ms |
15964 KB |
Output is correct |
52 |
Correct |
12 ms |
16004 KB |
Output is correct |
53 |
Correct |
11 ms |
15964 KB |
Output is correct |
54 |
Correct |
12 ms |
15960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
37628 KB |
Output is correct |
2 |
Correct |
50 ms |
37620 KB |
Output is correct |
3 |
Correct |
49 ms |
37620 KB |
Output is correct |
4 |
Correct |
49 ms |
37616 KB |
Output is correct |
5 |
Correct |
49 ms |
37620 KB |
Output is correct |
6 |
Correct |
14 ms |
18176 KB |
Output is correct |
7 |
Correct |
59 ms |
37440 KB |
Output is correct |
8 |
Correct |
44 ms |
32000 KB |
Output is correct |
9 |
Correct |
46 ms |
34644 KB |
Output is correct |
10 |
Correct |
47 ms |
34552 KB |
Output is correct |
11 |
Correct |
40 ms |
30720 KB |
Output is correct |
12 |
Correct |
11 ms |
15960 KB |
Output is correct |
13 |
Correct |
11 ms |
15964 KB |
Output is correct |
14 |
Correct |
11 ms |
15964 KB |
Output is correct |
15 |
Correct |
11 ms |
16004 KB |
Output is correct |
16 |
Correct |
11 ms |
15964 KB |
Output is correct |
17 |
Correct |
11 ms |
15964 KB |
Output is correct |
18 |
Correct |
11 ms |
16012 KB |
Output is correct |
19 |
Correct |
11 ms |
15964 KB |
Output is correct |
20 |
Correct |
11 ms |
15964 KB |
Output is correct |
21 |
Correct |
11 ms |
15996 KB |
Output is correct |
22 |
Correct |
11 ms |
15960 KB |
Output is correct |
23 |
Correct |
11 ms |
15960 KB |
Output is correct |
24 |
Correct |
12 ms |
15964 KB |
Output is correct |
25 |
Correct |
11 ms |
16004 KB |
Output is correct |
26 |
Correct |
11 ms |
15964 KB |
Output is correct |
27 |
Correct |
11 ms |
15964 KB |
Output is correct |
28 |
Correct |
11 ms |
15964 KB |
Output is correct |
29 |
Correct |
11 ms |
15964 KB |
Output is correct |
30 |
Correct |
11 ms |
15964 KB |
Output is correct |
31 |
Correct |
11 ms |
15964 KB |
Output is correct |
32 |
Correct |
11 ms |
16004 KB |
Output is correct |
33 |
Correct |
11 ms |
16000 KB |
Output is correct |
34 |
Correct |
11 ms |
15964 KB |
Output is correct |
35 |
Correct |
11 ms |
15964 KB |
Output is correct |
36 |
Correct |
11 ms |
15964 KB |
Output is correct |
37 |
Correct |
11 ms |
15996 KB |
Output is correct |
38 |
Correct |
11 ms |
16024 KB |
Output is correct |
39 |
Correct |
11 ms |
15964 KB |
Output is correct |
40 |
Correct |
11 ms |
16016 KB |
Output is correct |
41 |
Correct |
11 ms |
16220 KB |
Output is correct |
42 |
Correct |
11 ms |
15964 KB |
Output is correct |
43 |
Correct |
11 ms |
15964 KB |
Output is correct |
44 |
Correct |
11 ms |
15964 KB |
Output is correct |
45 |
Correct |
11 ms |
15964 KB |
Output is correct |
46 |
Correct |
11 ms |
15996 KB |
Output is correct |
47 |
Correct |
12 ms |
15964 KB |
Output is correct |
48 |
Correct |
11 ms |
15964 KB |
Output is correct |
49 |
Correct |
12 ms |
15996 KB |
Output is correct |
50 |
Correct |
11 ms |
15960 KB |
Output is correct |
51 |
Correct |
11 ms |
15964 KB |
Output is correct |
52 |
Correct |
11 ms |
16216 KB |
Output is correct |
53 |
Correct |
11 ms |
15992 KB |
Output is correct |
54 |
Correct |
12 ms |
16000 KB |
Output is correct |