Submission #38519

#	Time	Username	Problem	Language	Result	Execution time	Memory
38519		Waschbar	Three Friends (BOI14_friends)	C++14	100 / 100	149 ms	7860 KiB

friends

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

int cnt[100];
//AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
int main() {
	
	string s;
	int n;
	cin >> n;
	cin >> s;
	//n = s.length();
	//cout << n << endl;
	
	if(n%2 == 0) {
		cout << "NOT POSSIBLE";
		return 0;
	}
	
	for(int i = 0; i < n; i++)
		cnt[s[i]-'A']++;
	
	char ch;
	int tmp = 0;
	for(int i = 0; i < 30; i++) 
		if(cnt[i]%2) tmp++,ch = (char)('A'+i);
	
	if(tmp != 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] == ch){
			y1 = x1;
			break;
		}
		x1--; x2--;
	}
	if(x1 >= 0 && x2 <= n/2 && s[x1] == ch){
			y1 = x1; 
	}
	
	x1 = n/2-1; x2 = n-1;
	while(x1 >= 0 && x2 >= n/2) {
		if(s[x1] != s[x2] && s[x2] == ch){
			y2 = x2;
			break;
		}
		x1--; x2--;
	}
	if(x1 < 0 && x2 <= n/2 && s[x2] == ch){
			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++;
		}
	}
	
	//cout << y1 << " " << y2 << " " << ch << endl;
	
	
	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 (stderr)

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

• Subtask 1: 35 / 35
• Subtask 2: 65 / 65