Submission #105586

#	Time	Username	Problem	Language	Result	Execution time	Memory
105586		luciocf	Three Friends (BOI14_friends)	C++14	0 / 100	192 ms	8108 KiB

friends

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e6+10;

int n, m;

char S[maxn];

int last(string a, string b)
{
	for (int i = 0; i < a.size(); i++)
		if (a[i] != b[i]) 
			return i;

	return -1;
}

int solve1(void)
{
	string a = "", b = "";

	for (int i = 0; i <= m; i++)
		a += S[i];
	for (int i = m+1; i < n; i++)
		b += S[i];

	int pos = last(a, b);

	if (pos == -1)
	{
		if (S[m] == S[n-1]) return 2;
		return 1;
	}

	for (int i = pos+1; i < m; i++)
		if (b[i-1] != a[i])
			return 0;

	return 1;
}

int solve2(void)
{
	string a = "", b = "";

	for (int i = 0; i < m; i++)
		b += S[i];
	for (int i = m; i < n; i++)
		a += S[i];

	int pos = last(a, b);

	if (pos == -1)
	{
		if (S[m] == S[n-1]) return 2;
		return 1;
	}

	for (int i = pos+1; i <= m; i++)
	{
		if (b[i-1] != a[i])
			return 0;
	}

	return 1;
}

bool cmp(string a, string b)
{
	for (int i = 0; i < a.size(); i++)
		if (a[i] != b[i])
			return 0;

	return 1;
}

int main(void)
{
	scanf("%d", &n);
	m = n/2;

	for (int i = 0; i < n; i++)
		scanf(" %c", &S[i]);

	if (n%2 == 0)
	{
		printf("NOT POSSIBLE\n");
		return 0;
	}

	int ok1 = solve1();
	int ok2 = solve2();

	if (ok1 == 2 || ok2 == 2) printf("NOT UNIQUE\n");
	else if (!ok1 && !ok2) printf("NOT POSSIBLE\n");
	else if (ok1 && ok2)
	{
		string a = "", b = "";
		for (int i = 0; i < m; i++)
			a += S[i];
		for (int i = m+1; i < n; i++)
			b += S[i];

		if (!cmp(a, b)) printf("NOT UNIQUE\n");
		else cout << a << "\n";
	}
	else if (ok1)
	{
		for (int i = m+1; i < n; i++)
			printf("%c", S[i]);
		printf("\n");
	}
	else
	{
		for (int i = 0; i < m; i++)
			printf("%c", S[i]);
		printf("\n");
	}
}

Compilation message (stderr)

friends.cpp: In function 'int last(std::__cxx11::string, std::__cxx11::string)':
friends.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++)
                  ~~^~~~~~~~~~
friends.cpp: In function 'bool cmp(std::__cxx11::string, std::__cxx11::string)':
friends.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++)
                  ~~^~~~~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
friends.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &S[i]);
   ~~~~~^~~~~~~~~~~~~~

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