Submission #38536

#	Time	Username	Problem	Language	Result	Execution time	Memory
38536		oTTo_22	Three Friends (BOI14_friends)	C++14	100 / 100	209 ms	7864 KiB

friends

#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 (stderr)

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 / 35
• Subtask 2: 65 / 65