Submission #42942

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
42942	2018-03-06T15:10:18 Z	ruhanhabib39	Three Friends (BOI14_friends)	C++14	100 / 100	91 ms	21788 KB

friends

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5+1;

int N;
string inp;

// [i, j), [l, r)
bool oka(int i, int j, int l, int r) {
   while(i < j) {
      while(l < r && inp[i] != inp[l]) l++;
      if(l >= r) break;
      i++; l++;
   }
   return i == j;
}

string solve() {
   const string notPossible = "NOT POSSIBLE";
   const string notUnique = "NOT UNIQUE";

   if(N % 2 == 0) return notPossible;
   int m = N / 2;
   bool okA = oka(0, m, m, N);
   bool okB = oka(m+1, N, 0, m+1);
   if(!okA && !okB) return notPossible;
   if(okA && okB && inp.substr(0, m) != inp.substr(m+1, m)) return notUnique;
   if(okA) return inp.substr(0, m);
   return inp.substr(m+1, m);
}

int main() {
   cin >> N >> inp;
   cout << solve() << endl;
}

Subtask #1

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	356 KB	Output is correct
3	Correct	1 ms	432 KB	Output is correct
4	Correct	1 ms	432 KB	Output is correct
5	Correct	1 ms	456 KB	Output is correct
6	Correct	1 ms	456 KB	Output is correct
7	Correct	2 ms	552 KB	Output is correct
8	Correct	2 ms	660 KB	Output is correct
9	Correct	1 ms	660 KB	Output is correct
10	Correct	1 ms	660 KB	Output is correct
11	Correct	1 ms	660 KB	Output is correct
12	Correct	2 ms	660 KB	Output is correct
13	Correct	1 ms	660 KB	Output is correct
14	Correct	2 ms	700 KB	Output is correct
15	Correct	1 ms	700 KB	Output is correct
16	Correct	2 ms	700 KB	Output is correct
17	Correct	2 ms	700 KB	Output is correct
18	Correct	1 ms	880 KB	Output is correct
19	Correct	1 ms	880 KB	Output is correct
20	Correct	1 ms	880 KB	Output is correct
21	Correct	1 ms	880 KB	Output is correct
22	Correct	1 ms	880 KB	Output is correct
23	Correct	1 ms	880 KB	Output is correct
24	Correct	1 ms	880 KB	Output is correct
25	Correct	1 ms	880 KB	Output is correct
26	Correct	1 ms	880 KB	Output is correct
27	Correct	1 ms	880 KB	Output is correct
28	Correct	1 ms	880 KB	Output is correct
29	Correct	1 ms	880 KB	Output is correct
30	Correct	2 ms	880 KB	Output is correct
31	Correct	1 ms	880 KB	Output is correct
32	Correct	1 ms	880 KB	Output is correct
33	Correct	1 ms	880 KB	Output is correct
34	Correct	1 ms	880 KB	Output is correct
35	Correct	1 ms	880 KB	Output is correct
36	Correct	1 ms	880 KB	Output is correct
37	Correct	2 ms	880 KB	Output is correct
38	Correct	1 ms	880 KB	Output is correct
39	Correct	1 ms	880 KB	Output is correct
40	Correct	2 ms	880 KB	Output is correct
41	Correct	2 ms	880 KB	Output is correct
42	Correct	2 ms	880 KB	Output is correct
43	Correct	1 ms	880 KB	Output is correct
44	Correct	2 ms	880 KB	Output is correct
45	Correct	2 ms	896 KB	Output is correct
46	Correct	2 ms	896 KB	Output is correct
47	Correct	2 ms	896 KB	Output is correct
48	Correct	2 ms	908 KB	Output is correct
49	Correct	2 ms	912 KB	Output is correct
50	Correct	2 ms	920 KB	Output is correct
51	Correct	1 ms	1048 KB	Output is correct
52	Correct	2 ms	1048 KB	Output is correct
53	Correct	2 ms	1048 KB	Output is correct
54	Correct	1 ms	1048 KB	Output is correct

Subtask #2

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	5216 KB	Output is correct
2	Correct	73 ms	7140 KB	Output is correct
3	Correct	83 ms	9176 KB	Output is correct
4	Correct	79 ms	11100 KB	Output is correct
5	Correct	91 ms	13060 KB	Output is correct
6	Correct	74 ms	15012 KB	Output is correct
7	Correct	74 ms	17856 KB	Output is correct
8	Correct	64 ms	18300 KB	Output is correct
9	Correct	74 ms	20188 KB	Output is correct
10	Correct	66 ms	21760 KB	Output is correct
11	Correct	88 ms	21788 KB	Output is correct
12	Correct	1 ms	21788 KB	Output is correct
13	Correct	1 ms	21788 KB	Output is correct
14	Correct	1 ms	21788 KB	Output is correct
15	Correct	2 ms	21788 KB	Output is correct
16	Correct	1 ms	21788 KB	Output is correct
17	Correct	1 ms	21788 KB	Output is correct
18	Correct	2 ms	21788 KB	Output is correct
19	Correct	2 ms	21788 KB	Output is correct
20	Correct	1 ms	21788 KB	Output is correct
21	Correct	2 ms	21788 KB	Output is correct
22	Correct	1 ms	21788 KB	Output is correct
23	Correct	1 ms	21788 KB	Output is correct
24	Correct	2 ms	21788 KB	Output is correct
25	Correct	2 ms	21788 KB	Output is correct
26	Correct	2 ms	21788 KB	Output is correct
27	Correct	2 ms	21788 KB	Output is correct
28	Correct	1 ms	21788 KB	Output is correct
29	Correct	1 ms	21788 KB	Output is correct
30	Correct	1 ms	21788 KB	Output is correct
31	Correct	1 ms	21788 KB	Output is correct
32	Correct	2 ms	21788 KB	Output is correct
33	Correct	2 ms	21788 KB	Output is correct
34	Correct	2 ms	21788 KB	Output is correct
35	Correct	1 ms	21788 KB	Output is correct
36	Correct	2 ms	21788 KB	Output is correct
37	Correct	2 ms	21788 KB	Output is correct
38	Correct	2 ms	21788 KB	Output is correct
39	Correct	1 ms	21788 KB	Output is correct
40	Correct	1 ms	21788 KB	Output is correct
41	Correct	1 ms	21788 KB	Output is correct
42	Correct	1 ms	21788 KB	Output is correct
43	Correct	1 ms	21788 KB	Output is correct
44	Correct	2 ms	21788 KB	Output is correct
45	Correct	2 ms	21788 KB	Output is correct
46	Correct	2 ms	21788 KB	Output is correct
47	Correct	2 ms	21788 KB	Output is correct
48	Correct	2 ms	21788 KB	Output is correct
49	Correct	2 ms	21788 KB	Output is correct
50	Correct	1 ms	21788 KB	Output is correct
51	Correct	1 ms	21788 KB	Output is correct
52	Correct	2 ms	21788 KB	Output is correct
53	Correct	2 ms	21788 KB	Output is correct
54	Correct	2 ms	21788 KB	Output is correct