oj.uz

Submission #339258

# Submission time Handle Problem Language Result Execution time Memory
339258 2020-12-25T01:49:06 Z nandonathaniel Three Friends (BOI14_friends) C++14
100 / 100
 88 ms 22032 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2000005,MOD=1e9+7;

int pref[MAXN],pkt[MAXN];
set<int> S;

int get(int L,int R){
	L++;R++;
	if(L>R)return 0;
	return (pref[R]-((1LL*pref[L-1]*pkt[R-L+1])%MOD)+MOD)%MOD;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	string s;
	cin >> n >> s;
	if(n%2==0){
		cout << "NOT POSSIBLE\n";
		return 0;
	}
	pkt[0]=1;
	for(int i=0;i<n;i++){
		pref[i+1]=(26LL*pref[i]+s[i]-'A')%MOD;
		pkt[i+1]=(26LL*pkt[i])%MOD;
	}
	int idxL,idxR;
	for(int i=1;i<n-1;i++){
		int kiri=0,kanan=0;
		if(i<=n/2){
			kiri=(((1LL*pkt[n/2-i]*get(0,i-1))%MOD)+get(i+1,i+n/2-i))%MOD;
			kanan=get(n/2+1,n-1);
		}
		else{
			kiri=get(0,n/2-1);
			kanan=(((1LL*pkt[n-i-1]*get(n/2,i-1))%MOD)+get(i+1,n-1))%MOD;
		}
		if(kiri==kanan){
			S.insert(kiri);
			if(i<=n/2){
				idxL=n/2+1;idxR=n-1;
			}
			else{
				idxL=0;idxR=n/2-1;
			}
		}
	}
	int kiri=get(1,n/2),kanan=get(n/2+1,n-1);
	if(kiri==kanan){
		S.insert(kiri);
		idxL=1;idxR=n/2;
	}
	kiri=get(0,n/2-1);kanan=get(n/2,n-2);
	if(kiri==kanan){
		S.insert(kiri);
		idxL=0;idxR=n/2-1;
	}
	if(S.size()==0){
		cout << "NOT POSSIBLE\n";
	}
	else if(S.size()==1){
		cout << s.substr(idxL,idxR-idxL+1) << '\n';
	}
	else cout << "NOT UNIQUE\n";
	return 0;
}

Compilation message

friends.cpp: In function 'int main()':
friends.cpp:63:29: warning: 'idxR' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |   cout << s.substr(idxL,idxR-idxL+1) << '\n';
      |                         ~~~~^~~~~
friends.cpp:63:19: warning: 'idxL' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |   cout << s.substr(idxL,idxR-idxL+1) << '\n';
      |           ~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
35.0 / 35.0

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

Subtask #2
65.0 / 65.0

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