답안 #41196 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41196	2018-02-13T17:52:27 Z	IvanC	세 명의 친구들 (BOI14_friends)	C++14	100 / 100	211 ms	80276 KB

friends

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MOD1 = 1e9 + 9;
const ll prime1 = 999983;
const ll invprime1 = 943912055;
const int MAXN = 2000011;
ll N,hash1[MAXN],pot1[MAXN],invpot1[MAXN];
vector<ll> possiveis;
set<ll> valores;
string S;
ll get_hash(ll a,ll b){
	if(a > b) return 0;
	ll val = hash1[b] - hash1[a-1];
	if(val < 0) val += MOD1;
	val *= invpot1[a-1];
	return val % MOD1;
}
void checa(int pos){
	if(pos == N/2 + 1){
		if(get_hash(1,pos-1) == get_hash(pos+1,N)){
			possiveis.push_back(pos-1);
			valores.insert(get_hash(1,pos-1));
		}
	}
	else if(pos <= N/2){
		int resta = pos - 1;
		ll val1 = get_hash(1,pos - 1);
		int falta = N/2 - resta;
		ll val2 = get_hash(pos + 1,pos + falta);
		ll val3 = (val1 + pot1[resta]*val2) % MOD1;
		ll val4 = get_hash(pos+falta+1,N);
		if(val3 == val4){
			possiveis.push_back(pos-1);
			valores.insert(val4);
		}
	} 
	else{
		int resta = N - pos;
		ll val1 = get_hash(pos+1,N);
		int falta = N/2 - resta;
		ll val2 = get_hash(pos - falta,pos-1);
		ll val3 = (val2 + pot1[falta]*val1) % MOD1;
		ll val4 = get_hash(1,pos - falta - 1);
		if(val3 == val4){
			possiveis.push_back(pos-1);
			valores.insert(val4);
		}
	}
}
int main(){
	cin >> N >> S;
	if(N == 2){
		if(S[0] == S[1]) cout << S[0] << endl;
		else cout << "NOT UNIQUE" << endl;
		return 0;
	}
	if(N % 2 != 1){
		cout << "NOT POSSIBLE" << endl;
		return 0;
	}
	pot1[0] = invpot1[0] = 1;
	for(int i = 1;i<=N;i++){
		invpot1[i] = (invpot1[i-1]*invprime1) % MOD1;
		pot1[i] = (pot1[i-1]*prime1) % MOD1;
		hash1[i] = (hash1[i-1] + pot1[i]*S[i-1]) % MOD1;
	}
	for(int i = 1;i<=N;i++) checa(i);
	if(valores.size() == 0){
		cout << "NOT POSSIBLE" << endl;
		return 0;
	}
	else if(valores.size() > 1){
		cout << "NOT UNIQUE" << endl;
		return 0;
	}
	else{
		S.erase(S.begin() + possiveis[0]);
		S.resize(N/2);
		cout << S << endl;
	}
	return  0;
}

Subtask #1
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	424 KB	Output is correct
4	Correct	2 ms	440 KB	Output is correct
5	Correct	2 ms	476 KB	Output is correct
6	Correct	2 ms	476 KB	Output is correct
7	Correct	2 ms	476 KB	Output is correct
8	Correct	1 ms	476 KB	Output is correct
9	Correct	1 ms	476 KB	Output is correct
10	Correct	1 ms	476 KB	Output is correct
11	Correct	1 ms	476 KB	Output is correct
12	Correct	1 ms	476 KB	Output is correct
13	Correct	2 ms	476 KB	Output is correct
14	Correct	1 ms	584 KB	Output is correct
15	Correct	1 ms	584 KB	Output is correct
16	Correct	1 ms	584 KB	Output is correct
17	Correct	2 ms	644 KB	Output is correct
18	Correct	1 ms	644 KB	Output is correct
19	Correct	1 ms	644 KB	Output is correct
20	Correct	1 ms	644 KB	Output is correct
21	Correct	1 ms	676 KB	Output is correct
22	Correct	2 ms	676 KB	Output is correct
23	Correct	1 ms	676 KB	Output is correct
24	Correct	1 ms	676 KB	Output is correct
25	Correct	2 ms	676 KB	Output is correct
26	Correct	1 ms	676 KB	Output is correct
27	Correct	1 ms	676 KB	Output is correct
28	Correct	2 ms	676 KB	Output is correct
29	Correct	1 ms	676 KB	Output is correct
30	Correct	1 ms	676 KB	Output is correct
31	Correct	1 ms	676 KB	Output is correct
32	Correct	1 ms	676 KB	Output is correct
33	Correct	1 ms	676 KB	Output is correct
34	Correct	2 ms	676 KB	Output is correct
35	Correct	1 ms	676 KB	Output is correct
36	Correct	1 ms	676 KB	Output is correct
37	Correct	1 ms	676 KB	Output is correct
38	Correct	1 ms	676 KB	Output is correct
39	Correct	1 ms	676 KB	Output is correct
40	Correct	1 ms	676 KB	Output is correct
41	Correct	2 ms	676 KB	Output is correct
42	Correct	1 ms	676 KB	Output is correct
43	Correct	2 ms	676 KB	Output is correct
44	Correct	2 ms	676 KB	Output is correct
45	Correct	2 ms	676 KB	Output is correct
46	Correct	2 ms	676 KB	Output is correct
47	Correct	2 ms	676 KB	Output is correct
48	Correct	2 ms	676 KB	Output is correct
49	Correct	2 ms	676 KB	Output is correct
50	Correct	2 ms	676 KB	Output is correct
51	Correct	2 ms	676 KB	Output is correct
52	Correct	2 ms	676 KB	Output is correct
53	Correct	2 ms	676 KB	Output is correct
54	Correct	2 ms	676 KB	Output is correct

Subtask #2
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	160 ms	50680 KB	Output is correct
2	Correct	167 ms	52564 KB	Output is correct
3	Correct	185 ms	54564 KB	Output is correct
4	Correct	153 ms	56636 KB	Output is correct
5	Correct	156 ms	58504 KB	Output is correct
6	Correct	70 ms	58504 KB	Output is correct
7	Correct	211 ms	80276 KB	Output is correct
8	Correct	140 ms	80276 KB	Output is correct
9	Correct	137 ms	80276 KB	Output is correct
10	Correct	137 ms	80276 KB	Output is correct
11	Correct	137 ms	80276 KB	Output is correct
12	Correct	2 ms	80276 KB	Output is correct
13	Correct	2 ms	80276 KB	Output is correct
14	Correct	1 ms	80276 KB	Output is correct
15	Correct	2 ms	80276 KB	Output is correct
16	Correct	2 ms	80276 KB	Output is correct
17	Correct	2 ms	80276 KB	Output is correct
18	Correct	2 ms	80276 KB	Output is correct
19	Correct	1 ms	80276 KB	Output is correct
20	Correct	1 ms	80276 KB	Output is correct
21	Correct	1 ms	80276 KB	Output is correct
22	Correct	1 ms	80276 KB	Output is correct
23	Correct	1 ms	80276 KB	Output is correct
24	Correct	1 ms	80276 KB	Output is correct
25	Correct	2 ms	80276 KB	Output is correct
26	Correct	1 ms	80276 KB	Output is correct
27	Correct	1 ms	80276 KB	Output is correct
28	Correct	1 ms	80276 KB	Output is correct
29	Correct	1 ms	80276 KB	Output is correct
30	Correct	1 ms	80276 KB	Output is correct
31	Correct	2 ms	80276 KB	Output is correct
32	Correct	1 ms	80276 KB	Output is correct
33	Correct	1 ms	80276 KB	Output is correct
34	Correct	1 ms	80276 KB	Output is correct
35	Correct	1 ms	80276 KB	Output is correct
36	Correct	1 ms	80276 KB	Output is correct
37	Correct	2 ms	80276 KB	Output is correct
38	Correct	1 ms	80276 KB	Output is correct
39	Correct	2 ms	80276 KB	Output is correct
40	Correct	1 ms	80276 KB	Output is correct
41	Correct	2 ms	80276 KB	Output is correct
42	Correct	1 ms	80276 KB	Output is correct
43	Correct	1 ms	80276 KB	Output is correct
44	Correct	2 ms	80276 KB	Output is correct
45	Correct	2 ms	80276 KB	Output is correct
46	Correct	1 ms	80276 KB	Output is correct
47	Correct	1 ms	80276 KB	Output is correct
48	Correct	2 ms	80276 KB	Output is correct
49	Correct	1 ms	80276 KB	Output is correct
50	Correct	1 ms	80276 KB	Output is correct
51	Correct	2 ms	80276 KB	Output is correct
52	Correct	1 ms	80276 KB	Output is correct
53	Correct	2 ms	80276 KB	Output is correct
54	Correct	2 ms	80276 KB	Output is correct

답안 #41196

Compilation message

Subtask #1 35.0 / 35.0

Subtask #2 65.0 / 65.0

Subtask #1
35.0 / 35.0

Subtask #2
65.0 / 65.0