oj.uz

답안 #945730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945730 2024-03-14T06:49:24 Z phoenix0423 세 명의 친구들 (BOI14_friends) C++17
100 / 100
 44 ms 37628 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int INF = 1e9 + 7;
const int maxn = 2e6 + 5;
const int A = 923984352;
const int N = 998244353;
int p[maxn];

signed main(void){
	fastio;
	int n;
	cin>>n;
	p[0] = 1;
	for(int i = 1; i < n; i++) p[i] = p[i - 1] * A % N;
	string s;
	cin>>s;
	if(n % 2 == 0){
		cout<<"NOT POSSIBLE\n";
		return 0;
	}
	vector<int> h(n);
	h[0] = s[0];
	for(int i = 1; i < n; i++){
		h[i] = (h[i - 1] * A + s[i]) % N;
	}
	int len = n / 2;
	set<int> match;
	int ans = 0;
	for(int i = 0; i < n; i++){
		if(i <= len){
			int a = ((i ? h[i - 1] * p[len - i] : 0) + h[len] - h[i] * p[len - i] % N + N) % N;
			int b = (h[n - 1] - h[len] * p[len] % N + N) % N;
			if(a == b) match.insert(a), ans = i;
		}
		else{
			int a = h[len - 1];
			int b = ((h[n - 1] - h[i] * p[n - 1 - i] % N + N) + (h[i - 1] - h[len - 1] * p[i - len]) % N * p[n - 1 - i] % N + 2 * N) % N;
			if(a == b) match.insert(a), ans = i;
		}
	}
	if(match.size() >= 2){
		cout<<"NOT UNIQUE\n";
	}
	else if(!match.size()){
		cout<<"NOT POSSIBLE\n";
	}
	else{
		if(ans >= len) cout<<s.substr(0, len);
		else cout<<s.substr(len + 1, len);
		cout<<"\n";
	}
}

Subtask #1
35.0 / 35.0

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

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 37628 KB Output is correct
2 Correct 39 ms 37620 KB Output is correct
3 Correct 38 ms 37620 KB Output is correct
4 Correct 38 ms 37588 KB Output is correct
5 Correct 38 ms 37448 KB Output is correct
6 Correct 14 ms 19956 KB Output is correct
7 Correct 44 ms 37620 KB Output is correct
8 Correct 34 ms 32728 KB Output is correct
9 Correct 34 ms 34336 KB Output is correct
10 Correct 35 ms 34372 KB Output is correct
11 Correct 31 ms 31220 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 600 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 468 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 356 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 648 KB Output is correct
46 Correct 0 ms 460 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 1 ms 348 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct