# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
243827 | 2020-07-01T22:01:46 Z | kimbj0709 | Three Friends (BOI14_friends) | C++14 | 93 ms | 26736 KB |
#include <bits/stdc++.h> using namespace std; #define int long long #define mod 1000000009 #define po 179 #define maxn 2000050 vector<int> powers(maxn,1); int len; string find(string input){ string ret = ""; int can1 = 0; int currsum = 0; int target = 0; for(int i=1;i<len/2+1;i++){ currsum += (input.at(i)-'A')*powers[i-1]; currsum %= mod; } for(int i=len/2+1;i<len;i++){ target += (input.at(i)-'A')*powers[i-len/2-1]; target %= mod; } if(currsum==target){ can1++; } for(int i=0;i<len/2;i++){ currsum -= (input.at(i+1)-'A')*powers[i]; currsum += (input.at(i)-'A')*powers[i]; currsum %= mod; currsum += mod*2; currsum %= mod; if(currsum==target){ can1++; } } if(can1>0){ for(int j=input.length()-1;j>input.length()-1-input.length()/2;j--){ ret += input.at(j); } reverse(ret.begin(),ret.end()); } return ret; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); string input; cin >> len >> input; if(len%2==0){ cout << "NOT POSSIBLE"; return 0; } for(int i=1;i<powers.size();i++){ powers[i] = powers[i-1]*po; powers[i] %= mod; } string temp1 = find(input); reverse(input.begin(),input.end()); string temp2 = find(input); reverse(temp2.begin(),temp2.end()); if(temp1.length()==0&&temp2.length()==0){ cout << "NOT POSSIBLE"; } else if(temp1.length()==0&&temp2.length()!=0){ cout << temp2; } else if(temp1.length()!=0&&temp2.length()==0){ cout << temp1; } else if(temp1!=temp2){ cout << "NOT UNIQUE"; } else{ cout << temp1; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 16000 KB | Output is correct |
2 | Correct | 28 ms | 16000 KB | Output is correct |
3 | Correct | 29 ms | 16000 KB | Output is correct |
4 | Correct | 28 ms | 16000 KB | Output is correct |
5 | Correct | 28 ms | 16000 KB | Output is correct |
6 | Correct | 29 ms | 16000 KB | Output is correct |
7 | Correct | 28 ms | 16000 KB | Output is correct |
8 | Correct | 28 ms | 16000 KB | Output is correct |
9 | Correct | 29 ms | 16000 KB | Output is correct |
10 | Correct | 29 ms | 16000 KB | Output is correct |
11 | Correct | 28 ms | 16000 KB | Output is correct |
12 | Correct | 28 ms | 16000 KB | Output is correct |
13 | Correct | 29 ms | 16000 KB | Output is correct |
14 | Correct | 29 ms | 16000 KB | Output is correct |
15 | Correct | 28 ms | 16000 KB | Output is correct |
16 | Correct | 29 ms | 16000 KB | Output is correct |
17 | Correct | 28 ms | 16000 KB | Output is correct |
18 | Correct | 30 ms | 16000 KB | Output is correct |
19 | Correct | 28 ms | 16000 KB | Output is correct |
20 | Correct | 28 ms | 16000 KB | Output is correct |
21 | Correct | 28 ms | 16000 KB | Output is correct |
22 | Correct | 28 ms | 16000 KB | Output is correct |
23 | Correct | 30 ms | 16000 KB | Output is correct |
24 | Correct | 12 ms | 16000 KB | Output is correct |
25 | Correct | 13 ms | 16000 KB | Output is correct |
26 | Correct | 12 ms | 16000 KB | Output is correct |
27 | Correct | 28 ms | 15872 KB | Output is correct |
28 | Correct | 28 ms | 16000 KB | Output is correct |
29 | Correct | 28 ms | 16000 KB | Output is correct |
30 | Correct | 28 ms | 16000 KB | Output is correct |
31 | Correct | 28 ms | 16000 KB | Output is correct |
32 | Correct | 28 ms | 16000 KB | Output is correct |
33 | Correct | 28 ms | 16000 KB | Output is correct |
34 | Correct | 28 ms | 16000 KB | Output is correct |
35 | Correct | 28 ms | 16000 KB | Output is correct |
36 | Correct | 28 ms | 16000 KB | Output is correct |
37 | Correct | 29 ms | 16000 KB | Output is correct |
38 | Correct | 28 ms | 16000 KB | Output is correct |
39 | Correct | 28 ms | 16000 KB | Output is correct |
40 | Correct | 28 ms | 16000 KB | Output is correct |
41 | Correct | 30 ms | 16000 KB | Output is correct |
42 | Correct | 28 ms | 16000 KB | Output is correct |
43 | Correct | 28 ms | 16000 KB | Output is correct |
44 | Correct | 29 ms | 16000 KB | Output is correct |
45 | Correct | 28 ms | 16000 KB | Output is correct |
46 | Correct | 28 ms | 16000 KB | Output is correct |
47 | Correct | 28 ms | 16000 KB | Output is correct |
48 | Correct | 28 ms | 16000 KB | Output is correct |
49 | Correct | 12 ms | 16000 KB | Output is correct |
50 | Correct | 29 ms | 16000 KB | Output is correct |
51 | Correct | 29 ms | 16000 KB | Output is correct |
52 | Correct | 30 ms | 16000 KB | Output is correct |
53 | Correct | 28 ms | 16000 KB | Output is correct |
54 | Correct | 29 ms | 16000 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 86 ms | 22788 KB | Output is correct |
2 | Correct | 83 ms | 22940 KB | Output is correct |
3 | Correct | 87 ms | 24860 KB | Output is correct |
4 | Correct | 84 ms | 24728 KB | Output is correct |
5 | Correct | 86 ms | 24732 KB | Output is correct |
6 | Correct | 20 ms | 19996 KB | Output is correct |
7 | Correct | 93 ms | 26736 KB | Output is correct |
8 | Correct | 85 ms | 23992 KB | Output is correct |
9 | Correct | 81 ms | 24100 KB | Output is correct |
10 | Correct | 79 ms | 23996 KB | Output is correct |
11 | Correct | 68 ms | 21020 KB | Output is correct |
12 | Correct | 29 ms | 16000 KB | Output is correct |
13 | Correct | 28 ms | 16000 KB | Output is correct |
14 | Correct | 29 ms | 16000 KB | Output is correct |
15 | Correct | 29 ms | 16000 KB | Output is correct |
16 | Correct | 29 ms | 16000 KB | Output is correct |
17 | Correct | 30 ms | 16000 KB | Output is correct |
18 | Correct | 29 ms | 16000 KB | Output is correct |
19 | Correct | 29 ms | 16128 KB | Output is correct |
20 | Correct | 28 ms | 16000 KB | Output is correct |
21 | Correct | 28 ms | 16000 KB | Output is correct |
22 | Correct | 28 ms | 16000 KB | Output is correct |
23 | Correct | 28 ms | 16000 KB | Output is correct |
24 | Correct | 28 ms | 16000 KB | Output is correct |
25 | Correct | 28 ms | 16000 KB | Output is correct |
26 | Correct | 29 ms | 16000 KB | Output is correct |
27 | Correct | 28 ms | 16000 KB | Output is correct |
28 | Correct | 28 ms | 16000 KB | Output is correct |
29 | Correct | 29 ms | 16000 KB | Output is correct |
30 | Correct | 30 ms | 16000 KB | Output is correct |
31 | Correct | 28 ms | 16000 KB | Output is correct |
32 | Correct | 28 ms | 16000 KB | Output is correct |
33 | Correct | 29 ms | 16000 KB | Output is correct |
34 | Correct | 34 ms | 16000 KB | Output is correct |
35 | Correct | 13 ms | 16000 KB | Output is correct |
36 | Correct | 16 ms | 16000 KB | Output is correct |
37 | Correct | 14 ms | 16000 KB | Output is correct |
38 | Correct | 29 ms | 16000 KB | Output is correct |
39 | Correct | 28 ms | 16000 KB | Output is correct |
40 | Correct | 29 ms | 16000 KB | Output is correct |
41 | Correct | 29 ms | 16000 KB | Output is correct |
42 | Correct | 28 ms | 16000 KB | Output is correct |
43 | Correct | 28 ms | 16000 KB | Output is correct |
44 | Correct | 28 ms | 16000 KB | Output is correct |
45 | Correct | 29 ms | 16000 KB | Output is correct |
46 | Correct | 28 ms | 16000 KB | Output is correct |
47 | Correct | 29 ms | 16128 KB | Output is correct |
48 | Correct | 31 ms | 16000 KB | Output is correct |
49 | Correct | 28 ms | 16000 KB | Output is correct |
50 | Correct | 28 ms | 16000 KB | Output is correct |
51 | Correct | 29 ms | 16000 KB | Output is correct |
52 | Correct | 31 ms | 16000 KB | Output is correct |
53 | Correct | 29 ms | 16000 KB | Output is correct |
54 | Correct | 28 ms | 16000 KB | Output is correct |