Submission #118588

#	Time	Username	Problem	Language	Result	Execution time	Memory
118588		onjo0127	Three Friends (BOI14_friends)	C++11	100 / 100	80 ms	11128 KiB

friends

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

char S[2000009];
bool A[1000009], B[1000009], LA[1000009], LB[1000009], RA[1000009], RB[1000009];
int N, h;

bool chk(int p) {
	string s, t;
	for(int i=1, j=1; i<=N; i++) {
		if(i == p) continue;
		if(j > h) s += S[i];
		else t += S[i], ++j;
	}
	if(s == t) return 1;
	return 0;
}

void putans(int p) {
	for(int i=1, j=1; i<=N; i++) {
		if(p != i && j <= h) {
			printf("%c", S[i]);
			++j;
		}
	}
	exit(0);
}

int main() {
	bool fl = 1;
	scanf("%d %s", &N, S+1);
	if(N%2 == 0) return !printf("NOT POSSIBLE");
	h = N/2;
	for(int i=1; i<=N; i++) if(S[i] != S[1]) fl = 0;
	if(fl) putans(1);
	for(int i=1; i<=h+1; i++) A[i] = (S[i] == S[i+h]), B[i] = (S[i] == S[i+h+1]);
	LA[0] = LB[0] = RA[h+2] = RB[h+1] = 1;
	for(int i=1; i<=h+1; i++) LA[i] = LA[i-1] & A[i], LB[i] = LB[i-1] & B[i];
	for(int i=h+1; i>=1; i--) RA[i] = RA[i+1] & A[i], RB[i-1] = RB[i] & B[i-1];
	int c = 0;
	vector<int> p;
	for(int i=1; i<=h+1; i++) {
		if(LB[i-1] && RA[i+1] && i<=h) ++c, p.push_back(i);
		if(LA[i-1] && RB[i]) ++c, p.push_back(i + h);
	}
	sort(p.begin(), p.end());
	if(c >= 2 && p[0] == 1 && p.back() == N) puts("NOT UNIQUE");
	else if(c == 0) puts("NOT POSSIBLE");
	else putans(p[0]);
	return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %s", &N, S+1);
  ~~~~~^~~~~~~~~~~~~~~~~~

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