oj.uz

Submission #105595

# Submission time Handle Problem Language Result Execution time Memory
105595 2019-04-13T17:59:52 Z luciocf Three Friends (BOI14_friends) C++14
100 / 100
 225 ms 8224 KB 
#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 < m; i++)
		if (a[i] != b[i])
			return i;

	return -1;
}

bool 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) return 1;

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

	return 1;
}

bool 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) 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;
	}

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

	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 if (ok2)
	{
		for (int i = 0; i < m; i++)
			printf("%c", S[i]);
		printf("\n");
	}
}

Compilation message

friends.cpp: In function 'bool cmp(std::__cxx11::string, std::__cxx11::string)':
friends.cpp:62: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:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
friends.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &S[i]);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
35.0 / 35.0

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

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 7168 KB Output is correct
2 Correct 185 ms 7192 KB Output is correct
3 Correct 190 ms 7192 KB Output is correct
4 Correct 225 ms 7196 KB Output is correct
5 Correct 206 ms 7228 KB Output is correct
6 Correct 112 ms 2356 KB Output is correct
7 Correct 156 ms 8224 KB Output is correct
8 Correct 131 ms 5784 KB Output is correct
9 Correct 164 ms 5744 KB Output is correct
10 Correct 165 ms 7540 KB Output is correct
11 Correct 132 ms 7084 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 2 ms 256 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Correct 2 ms 256 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 256 KB Output is correct
31 Correct 0 ms 256 KB Output is correct
32 Correct 2 ms 256 KB Output is correct
33 Correct 3 ms 384 KB Output is correct
34 Correct 3 ms 256 KB Output is correct
35 Correct 2 ms 256 KB Output is correct
36 Correct 2 ms 384 KB Output is correct
37 Correct 2 ms 256 KB Output is correct
38 Correct 2 ms 256 KB Output is correct
39 Correct 3 ms 256 KB Output is correct
40 Correct 3 ms 256 KB Output is correct
41 Correct 3 ms 384 KB Output is correct
42 Correct 2 ms 256 KB Output is correct
43 Correct 1 ms 384 KB Output is correct
44 Correct 2 ms 256 KB Output is correct
45 Correct 3 ms 256 KB Output is correct
46 Correct 2 ms 256 KB Output is correct
47 Correct 2 ms 256 KB Output is correct
48 Correct 3 ms 384 KB Output is correct
49 Correct 2 ms 384 KB Output is correct
50 Correct 3 ms 384 KB Output is correct
51 Correct 2 ms 384 KB Output is correct
52 Correct 2 ms 384 KB Output is correct
53 Correct 2 ms 384 KB Output is correct
54 Correct 2 ms 384 KB Output is correct