oj.uz

Submission #38536

# Submission time Handle Problem Language Result Execution time Memory
38536 2018-01-04T11:33:39 Z oTTo_22 Three Friends (BOI14_friends) C++14
100 / 100
 209 ms 7864 KB 
#include <bits/stdc++.h>
using namespace std;

map < char,int > mp;

int main() {

	string s;
	int n;
	cin >> n >> s;

	if(n%2==0) {
        cout << "NOT POSSIBLE";
		return 0;
	}

	for(int i=0; i<n; i++)
		mp[s[i]]++;

	char c;
	int cnt=0;
	for (int i='A'; i<='Z'; i++)
        if (mp[i]%2) {
            cnt++;
            c=i;
        }

	if(cnt!=1) {
		cout << "NOT POSSIBLE";
		return 0;
	}

	int x1,x2,y1,y2;
	bool ind=0;
	x1=n/2;
	x2=n-1;
	y1=y2=-1;
	while(x1>=0 && x2>n/2) {
		if(s[x1]!=s[x2] && s[x1]==c){
			y1=x1;
			break;
		}
		x1--;
		x2--;
	}
	if(x1>=0 && x2<=n/2 && s[x1]==c)
        y1=x1;

	x1=n/2-1;
	x2=n-1;
	while(x1>=0 && x2>=n/2) {
		if(s[x1]!=s[x2] && s[x2]==c){
			y2=x2;
			break;
		}
		x1--;
		x2--;
	}
	if(x1<0 && x2<=n/2 && s[x2]==c)
        y2=x2;

	if(y1!=-1) {
		x1=0;
        x2=n/2+1;
		if(x1==y1)
            x1++;
		while(x1<=n/2){
			if(s[x1]!=s[x2]) {
			    y1=-1;
                break;
            }
			x1++;
			x2++;
			if(x1==y1)
                x1++;
		}
	}
	if(y2!=-1) {
		x1 = 0;
		x2 = n/2;
		if(x2 == y2)
            x2++;
		while(x1<n/2) {
			if(s[x1]!=s[x2]) {
			    y2=-1;
                break;
            }
			x1++;
			x2++;
			if(x2==y2)
                x2++;
		}
	}

	if(y1==-1 && y2==-1) {
		cout << "NOT POSSIBLE";
		return 0;
	}

	bool b1,b2;
	b1=b2=0;
	if(y1!=-1) {
		x1=0;
		x2=n/2+1;
		if(x1==y1)
            x1++;
		while(x1<=n/2){
			if(s[x1]!=s[x2]){
				b1=1;
				break;
			}
			x1++;
            x2++;
			if(x1==y1)
                x1++;
		}
	}
	if(y2!=-1){
		x1 = 0;
		x2 = n/2;
		if(x2 == y2) x2++;
		while(x1 < n/2) {
			if(s[x1] != s[x2]) {
				b2 = 1;
				break;
			}
			x1++; x2++;
			if(x2 == y2) x2++;
		}
	}

	if(y1 != -1 && y2 != -1 && b1 == 1 && b2 == 1) {
      cout<<"NOT POSSIBLE";
      return 0;
    }
	if(y1 != -1 && y2 == -1 && b1 == 1) {
      cout<<"NOT POSSIBLE";
      return 0;
    }
	if(y1 == -1 && y2 != -1 && b2 == 1) {
      cout<<"NOT POSSIBLE";
      return 0;
    }

	char s1[n/2], s2[n/2];

	if(y1 != -1) {
		x1 = 0; x2 = n/2+1;
		if(x1 == y1) x1++;
		while(x1 <= n/2) {
			s1[x2-n/2-1] = s[x1];
			x1++; x2++;
			if(x1 == y1) x1++;
		}
	}
	if(y2 != -1) {
		x1 = 0; x2 = n/2;
		if(x2 == y2) x2++;
		while(x1 < n/2) {
			s2[x1] = s[x2];
			if(s[x1] != s[x2]) break;
			x1++; x2++;
			if(x2 == y2) x2++;
		}
	}

	if(y1 != -1 && y2 != -1){
		bool bl = 1;
		for(int i = 0; i < n/2; i++){
			if(s1[i] != s2[i]){
				bl = 0;
				break;
			}
		}
		if(!bl){
			cout << "NOT UNIQUE";
			return 0;
		}
	}

	if(y1 != -1) {
		for(int i = 0; i < n/2; i++)
		cout << s1[i];
	}
	else {
		for(int i = 0; i < n/2; i++)
		cout << s2[i];
	}

}

Compilation message

friends.cpp: In function 'int main()':
friends.cpp:34:7: warning: unused variable 'ind' [-Wunused-variable]
  bool ind=0;
       ^
friends.cpp:39:19: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(s[x1]!=s[x2] && s[x1]==c){
                   ^

Subtask #1
35.0 / 35.0

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

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 7864 KB Output is correct
2 Correct 209 ms 7864 KB Output is correct
3 Correct 209 ms 7864 KB Output is correct
4 Correct 173 ms 7864 KB Output is correct
5 Correct 186 ms 7864 KB Output is correct
6 Correct 66 ms 7864 KB Output is correct
7 Correct 123 ms 7864 KB Output is correct
8 Correct 83 ms 5652 KB Output is correct
9 Correct 156 ms 5652 KB Output is correct
10 Correct 123 ms 5652 KB Output is correct
11 Correct 83 ms 4984 KB Output is correct
12 Correct 0 ms 2020 KB Output is correct
13 Correct 0 ms 2020 KB Output is correct
14 Correct 0 ms 2020 KB Output is correct
15 Correct 0 ms 2020 KB Output is correct
16 Correct 0 ms 2020 KB Output is correct
17 Correct 0 ms 2020 KB Output is correct
18 Correct 0 ms 2020 KB Output is correct
19 Correct 0 ms 2020 KB Output is correct
20 Correct 0 ms 2020 KB Output is correct
21 Correct 0 ms 2020 KB Output is correct
22 Correct 0 ms 2020 KB Output is correct
23 Correct 0 ms 2020 KB Output is correct
24 Correct 0 ms 2020 KB Output is correct
25 Correct 0 ms 2020 KB Output is correct
26 Correct 0 ms 2020 KB Output is correct
27 Correct 0 ms 2020 KB Output is correct
28 Correct 0 ms 2020 KB Output is correct
29 Correct 0 ms 2020 KB Output is correct
30 Correct 0 ms 2020 KB Output is correct
31 Correct 0 ms 2020 KB Output is correct
32 Correct 0 ms 2020 KB Output is correct
33 Correct 0 ms 2020 KB Output is correct
34 Correct 0 ms 2020 KB Output is correct
35 Correct 0 ms 2020 KB Output is correct
36 Correct 0 ms 2020 KB Output is correct
37 Correct 0 ms 2020 KB Output is correct
38 Correct 0 ms 2020 KB Output is correct
39 Correct 0 ms 2020 KB Output is correct
40 Correct 0 ms 2020 KB Output is correct
41 Correct 0 ms 2020 KB Output is correct
42 Correct 0 ms 2020 KB Output is correct
43 Correct 0 ms 2020 KB Output is correct
44 Correct 0 ms 2020 KB Output is correct
45 Correct 0 ms 2020 KB Output is correct
46 Correct 0 ms 2020 KB Output is correct
47 Correct 0 ms 2020 KB Output is correct
48 Correct 0 ms 2020 KB Output is correct
49 Correct 0 ms 2020 KB Output is correct
50 Correct 0 ms 2020 KB Output is correct
51 Correct 0 ms 2020 KB Output is correct
52 Correct 0 ms 2020 KB Output is correct
53 Correct 0 ms 2020 KB Output is correct
54 Correct 0 ms 2020 KB Output is correct