Submission #46215

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
46215	2018-04-18T04:50:51 Z	arman_ferdous	Three Friends (BOI14_friends)	C++11	100 / 100	24 ms	10556 KB

friends

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

int n;
string s;
set<string> st;

// search for [l2,r2] in [l1,r1] with exactly one mismatch and skip it
bool match_and_skip(int l1, int r1, int l2, int r2) {
	int cnt = 0;
	string ret = "";
	while(l1 <= r1 && l2 <= r2) {
		if(s[l1] != s[l2]) cnt++, l2--;
		else ret += s[l1];
		if(cnt > 1) return false;
		l1++, l2++;
	} 
	if(cnt == 1 || (l1 <= r1 && cnt == 0)) st.insert(ret);
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> s;
	if(~n&1) { cout << "NOT POSSIBLE\n"; return 0; }
	int len = n>>1;

	match_and_skip(0,len,len+1,n-1);					// (.x..)(...)
	match_and_skip(len,n-1,0,len-1);					// (...)(..x.)

	if(st.size() == 0) cout << "NOT POSSIBLE\n";
	else if(st.size() > 1) cout << "NOT UNIQUE\n";
	else cout << *(st.begin()) << "\n";
	return 0;
}

Compilation message

friends.cpp: In function 'bool match_and_skip(int, int, int, int)':
friends.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1

35.0 / 35.0

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

Subtask #2

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	6292 KB	Output is correct
2	Correct	16 ms	6292 KB	Output is correct
3	Correct	17 ms	6292 KB	Output is correct
4	Correct	20 ms	6292 KB	Output is correct
5	Correct	18 ms	6292 KB	Output is correct
6	Correct	6 ms	6292 KB	Output is correct
7	Correct	22 ms	6592 KB	Output is correct
8	Correct	24 ms	6940 KB	Output is correct
9	Correct	20 ms	8772 KB	Output is correct
10	Correct	13 ms	10556 KB	Output is correct
11	Correct	7 ms	10556 KB	Output is correct
12	Correct	2 ms	10556 KB	Output is correct
13	Correct	2 ms	10556 KB	Output is correct
14	Correct	2 ms	10556 KB	Output is correct
15	Correct	2 ms	10556 KB	Output is correct
16	Correct	2 ms	10556 KB	Output is correct
17	Correct	2 ms	10556 KB	Output is correct
18	Correct	2 ms	10556 KB	Output is correct
19	Correct	2 ms	10556 KB	Output is correct
20	Correct	2 ms	10556 KB	Output is correct
21	Correct	2 ms	10556 KB	Output is correct
22	Correct	2 ms	10556 KB	Output is correct
23	Correct	2 ms	10556 KB	Output is correct
24	Correct	2 ms	10556 KB	Output is correct
25	Correct	2 ms	10556 KB	Output is correct
26	Correct	2 ms	10556 KB	Output is correct
27	Correct	2 ms	10556 KB	Output is correct
28	Correct	2 ms	10556 KB	Output is correct
29	Correct	2 ms	10556 KB	Output is correct
30	Correct	2 ms	10556 KB	Output is correct
31	Correct	2 ms	10556 KB	Output is correct
32	Correct	2 ms	10556 KB	Output is correct
33	Correct	2 ms	10556 KB	Output is correct
34	Correct	2 ms	10556 KB	Output is correct
35	Correct	2 ms	10556 KB	Output is correct
36	Correct	2 ms	10556 KB	Output is correct
37	Correct	2 ms	10556 KB	Output is correct
38	Correct	2 ms	10556 KB	Output is correct
39	Correct	2 ms	10556 KB	Output is correct
40	Correct	2 ms	10556 KB	Output is correct
41	Correct	2 ms	10556 KB	Output is correct
42	Correct	2 ms	10556 KB	Output is correct
43	Correct	2 ms	10556 KB	Output is correct
44	Correct	2 ms	10556 KB	Output is correct
45	Correct	2 ms	10556 KB	Output is correct
46	Correct	2 ms	10556 KB	Output is correct
47	Correct	2 ms	10556 KB	Output is correct
48	Correct	2 ms	10556 KB	Output is correct
49	Correct	2 ms	10556 KB	Output is correct
50	Correct	2 ms	10556 KB	Output is correct
51	Correct	2 ms	10556 KB	Output is correct
52	Correct	2 ms	10556 KB	Output is correct
53	Correct	2 ms	10556 KB	Output is correct
54	Correct	2 ms	10556 KB	Output is correct