oj.uz

Submission #584481

# Submission time Handle Problem Language Result Execution time Memory
584481 2022-06-27T12:56:30 Z anubhavdhar Three Friends (BOI14_friends) C++11
100 / 100
 74 ms 51472 KB 
#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first 
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double

using namespace std;

const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

const ll MOD = 1e9 + 7;
const ll MAXN = 2e6 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;

const ll MOD1 = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1400305337;

const ll p1 = 29;
const ll p2 = 31;
const ll p3 = 37;

ll P[4][MAXN + 1];

#define make_hash(a, b, c) make_pair(a, make_pair(b, c))
typedef pair<ll, pair<ll, ll>> hash_type;

hash_type hash_val(string S){
	ll h1 = 0, h2 = 0, h3 = 0;
	for(char c : S){
		h1 = (h1 * p1 + (c - 'A' + 1)) % MOD1;
		h2 = (h2 * p2 + (c - 'A' + 1)) % MOD2;
		h3 = (h3 * p3 + (c - 'A' + 1)) % MOD3;
	}
	return make_hash(h1, h2, h3);
}

int N;
string S;
hash_type pref, suf;

bool check_pref(){
	
	ll h1 = suf.ff;
	ll h2 = suf.ss.ff;
	ll h3 = suf.ss.ss;

	for(int i = N / 2, v = N / 2 - 1; i < N - 1; ++i, --v){
		h1 = (h1 + (S[i] - S[i + 1]) * P[1][v] % MOD1 + MOD1) % MOD1;
		h2 = (h2 + (S[i] - S[i + 1]) * P[2][v] % MOD2 + MOD2) % MOD2;
		h3 = (h3 + (S[i] - S[i + 1]) * P[3][v] % MOD3 + MOD3) % MOD3;
		if(make_hash(h1, h2, h3) == pref){
			return true;
		}
	}
	return false;
}

bool check_suf(){
	
	ll h1 = pref.ff;
	ll h2 = pref.ss.ff;
	ll h3 = pref.ss.ss;

	for(int i = N / 2, v = 0; i; --i, ++v){
		h1 = (h1 + (S[i] - S[i - 1]) * P[1][v] % MOD1 + MOD1) % MOD1;
		h2 = (h2 + (S[i] - S[i - 1]) * P[2][v] % MOD2 + MOD2) % MOD2;
		h3 = (h3 + (S[i] - S[i - 1]) * P[3][v] % MOD3 + MOD3) % MOD3;
		if(make_hash(h1, h2, h3) == suf){
			return true;
		}
	}
	return false;
}

signed main(){

	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	

	P[1][0] = P[2][0] = P[3][0] = 1;
	F0Re(i, MAXN){
		P[1][i] = P[1][i - 1] * p1 % MOD1;
		P[2][i] = P[2][i - 1] * p2 % MOD2;
		P[3][i] = P[3][i - 1] * p3 % MOD3;
	}

	cin >> N >> S;
	if((N & 1) ^ 1){
		cout << "NOT POSSIBLE\n";
		exit(0);
	}

	pref = hash_val(S.substr(0, N / 2));
	suf = hash_val(S.substr(N / 2 + 1, N / 2));
	if(pref == suf){
		cout << S.substr(N / 2 + 1, N / 2) << '\n';
		exit(0);
	}

	bool t1 = check_pref();
	bool t2 = check_suf();

	if(t1 ^ t2){
		cout << (t1 ? S.substr(0, N / 2) : S.substr(N / 2 + 1, N / 2)) << '\n';
	}else{
		cout << "NOT " << (t1 ? "UNIQUE\n" : "POSSIBLE\n");
	}

	return 0;
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47180 KB Output is correct
2 Correct 28 ms 47216 KB Output is correct
3 Correct 28 ms 47152 KB Output is correct
4 Correct 29 ms 47252 KB Output is correct
5 Correct 30 ms 47216 KB Output is correct
6 Correct 29 ms 47268 KB Output is correct
7 Correct 30 ms 47252 KB Output is correct
8 Correct 29 ms 47180 KB Output is correct
9 Correct 29 ms 47196 KB Output is correct
10 Correct 29 ms 47264 KB Output is correct
11 Correct 29 ms 47260 KB Output is correct
12 Correct 35 ms 47200 KB Output is correct
13 Correct 31 ms 47260 KB Output is correct
14 Correct 32 ms 47288 KB Output is correct
15 Correct 31 ms 47180 KB Output is correct
16 Correct 32 ms 47252 KB Output is correct
17 Correct 30 ms 47224 KB Output is correct
18 Correct 29 ms 47236 KB Output is correct
19 Correct 30 ms 47180 KB Output is correct
20 Correct 31 ms 47296 KB Output is correct
21 Correct 30 ms 47160 KB Output is correct
22 Correct 30 ms 47188 KB Output is correct
23 Correct 30 ms 47180 KB Output is correct
24 Correct 35 ms 47240 KB Output is correct
25 Correct 30 ms 47276 KB Output is correct
26 Correct 30 ms 47188 KB Output is correct
27 Correct 30 ms 47220 KB Output is correct
28 Correct 29 ms 47172 KB Output is correct
29 Correct 29 ms 47180 KB Output is correct
30 Correct 31 ms 47312 KB Output is correct
31 Correct 36 ms 47228 KB Output is correct
32 Correct 32 ms 47228 KB Output is correct
33 Correct 30 ms 47180 KB Output is correct
34 Correct 29 ms 47188 KB Output is correct
35 Correct 31 ms 47188 KB Output is correct
36 Correct 29 ms 47180 KB Output is correct
37 Correct 31 ms 47200 KB Output is correct
38 Correct 29 ms 47156 KB Output is correct
39 Correct 31 ms 47172 KB Output is correct
40 Correct 30 ms 47188 KB Output is correct
41 Correct 30 ms 47152 KB Output is correct
42 Correct 29 ms 47208 KB Output is correct
43 Correct 29 ms 47188 KB Output is correct
44 Correct 29 ms 47208 KB Output is correct
45 Correct 30 ms 47188 KB Output is correct
46 Correct 29 ms 47188 KB Output is correct
47 Correct 29 ms 47264 KB Output is correct
48 Correct 29 ms 47228 KB Output is correct
49 Correct 29 ms 47200 KB Output is correct
50 Correct 34 ms 47184 KB Output is correct
51 Correct 31 ms 47180 KB Output is correct
52 Correct 30 ms 47188 KB Output is correct
53 Correct 30 ms 47268 KB Output is correct
54 Correct 30 ms 47248 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 51472 KB Output is correct
2 Correct 64 ms 51416 KB Output is correct
3 Correct 74 ms 51424 KB Output is correct
4 Correct 66 ms 51396 KB Output is correct
5 Correct 61 ms 51380 KB Output is correct
6 Correct 35 ms 49580 KB Output is correct
7 Correct 48 ms 51404 KB Output is correct
8 Correct 59 ms 50032 KB Output is correct
9 Correct 59 ms 50892 KB Output is correct
10 Correct 61 ms 50988 KB Output is correct
11 Correct 65 ms 49776 KB Output is correct
12 Correct 33 ms 47172 KB Output is correct
13 Correct 29 ms 47188 KB Output is correct
14 Correct 30 ms 47188 KB Output is correct
15 Correct 29 ms 47268 KB Output is correct
16 Correct 30 ms 47180 KB Output is correct
17 Correct 34 ms 47200 KB Output is correct
18 Correct 35 ms 47276 KB Output is correct
19 Correct 31 ms 47280 KB Output is correct
20 Correct 35 ms 47272 KB Output is correct
21 Correct 32 ms 47280 KB Output is correct
22 Correct 29 ms 47188 KB Output is correct
23 Correct 30 ms 47272 KB Output is correct
24 Correct 30 ms 47276 KB Output is correct
25 Correct 29 ms 47164 KB Output is correct
26 Correct 30 ms 47244 KB Output is correct
27 Correct 29 ms 47188 KB Output is correct
28 Correct 31 ms 47204 KB Output is correct
29 Correct 35 ms 47204 KB Output is correct
30 Correct 29 ms 47200 KB Output is correct
31 Correct 32 ms 47196 KB Output is correct
32 Correct 29 ms 47232 KB Output is correct
33 Correct 30 ms 47272 KB Output is correct
34 Correct 29 ms 47276 KB Output is correct
35 Correct 29 ms 47200 KB Output is correct
36 Correct 32 ms 47352 KB Output is correct
37 Correct 32 ms 47188 KB Output is correct
38 Correct 30 ms 47188 KB Output is correct
39 Correct 36 ms 47192 KB Output is correct
40 Correct 29 ms 47296 KB Output is correct
41 Correct 30 ms 47212 KB Output is correct
42 Correct 30 ms 47252 KB Output is correct
43 Correct 30 ms 47300 KB Output is correct
44 Correct 32 ms 47188 KB Output is correct
45 Correct 29 ms 47184 KB Output is correct
46 Correct 36 ms 47196 KB Output is correct
47 Correct 31 ms 47180 KB Output is correct
48 Correct 30 ms 47216 KB Output is correct
49 Correct 29 ms 47216 KB Output is correct
50 Correct 30 ms 47176 KB Output is correct
51 Correct 29 ms 47204 KB Output is correct
52 Correct 29 ms 47248 KB Output is correct
53 Correct 29 ms 47280 KB Output is correct
54 Correct 29 ms 47264 KB Output is correct