oj.uz

Submission #284783

# Submission time Handle Problem Language Result Execution time Memory
284783 2020-08-28T03:17:08 Z ChrisT Three Friends (BOI14_friends) C++17
100 / 100
 134 ms 20984 KB 
#include <bits/stdc++.h>
using namespace std;
const int MN = 2e6 + 5, MOD = 1e9 + 9, BASE = 143;
char s[MN]; int pw[MN], hsh[MN];
int substr (int l, int r) {
	if (r < l) return 0;
	int ret = hsh[r] - (long long)hsh[l-1] * pw[r-l+1] % MOD;
	if (ret < 0) ret += MOD;
	return ret;
}
int main () {
	int n;
	scanf ("%d",&n);
	scanf ("%s",s+1);
	if (!(n&1)) return !printf ("NOT POSSIBLE\n");
	pw[0] = 1;
	for (int i = 1; i <= n; i++) {
		pw[i] = (long long)pw[i-1] * BASE % MOD;
		hsh[i] = ((long long)hsh[i-1] * BASE + s[i] - 'A' + 1) % MOD;
	}
	int has = -1, where = -1;
	for (int i = 1; i <= (n+1)/2; i++) {
		int lhsh = ((long long)substr(1,i-1) * pw[n/2 - i + 1] + substr(i+1,n/2+1)) % MOD;
		int rhsh = substr(n/2+2,n);
		if (lhsh == rhsh) {
			if (~has && has != lhsh) return !printf ("NOT UNIQUE\n");
			has = lhsh; where = i;
		}
	}
	for (int i = n/2+2; i <= n; i++) {
		int lhsh = substr(1,n/2);
		int rhsh = ((long long)substr((n+1)/2,i-1) * pw[n-i] + substr(i+1,n)) % MOD;
		if (lhsh == rhsh) {
			if (~has && has != lhsh) return !printf ("NOT UNIQUE\n");
			has = lhsh; where = i;
		}
	}
	if (where == -1) return !printf ("NOT POSSIBLE\n");
	if (where > n/2) {
		for (int i = 1; i <= n/2; i++) printf ("%c",s[i]);
		printf ("\n");
	} else {
		for (int i = n/2+2; i <= n; i++) printf ("%c",s[i]);
		printf ("\n");
	}
	return 0;
}

Compilation message

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

Subtask #1
35.0 / 35.0

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

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 20864 KB Output is correct
2 Correct 132 ms 20856 KB Output is correct
3 Correct 125 ms 20856 KB Output is correct
4 Correct 126 ms 20856 KB Output is correct
5 Correct 126 ms 20856 KB Output is correct
6 Correct 10 ms 4224 KB Output is correct
7 Correct 134 ms 20984 KB Output is correct
8 Correct 65 ms 18040 KB Output is correct
9 Correct 117 ms 18808 KB Output is correct
10 Correct 118 ms 18912 KB Output is correct
11 Correct 61 ms 16632 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 0 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 0 ms 384 KB Output is correct
39 Correct 1 ms 384 KB Output is correct
40 Correct 1 ms 384 KB Output is correct
41 Correct 0 ms 384 KB Output is correct
42 Correct 1 ms 384 KB Output is correct
43 Correct 1 ms 384 KB Output is correct
44 Correct 1 ms 384 KB Output is correct
45 Correct 0 ms 384 KB Output is correct
46 Correct 0 ms 384 KB Output is correct
47 Correct 1 ms 384 KB Output is correct
48 Correct 1 ms 384 KB Output is correct
49 Correct 1 ms 384 KB Output is correct
50 Correct 0 ms 384 KB Output is correct
51 Correct 1 ms 384 KB Output is correct
52 Correct 1 ms 384 KB Output is correct
53 Correct 1 ms 384 KB Output is correct
54 Correct 0 ms 384 KB Output is correct