oj.uz

Submission #103508

# Submission time Handle Problem Language Result Execution time Memory
103508 2019-03-30T20:42:35 Z wilwxk Three Friends (BOI14_friends) C++11
100 / 100
 342 ms 75900 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAXN=2e6+6;
const ll MOD=1e9+7;
const ll P=257;
const ll P2=5;
char v[MAXN];
ll h[2][MAXN], pot[2][MAXN];
unordered_set<ll> s;
int n;
 
ll gh(int ini, int fim, int k) {
	if(fim<ini) return 0;
	ll val=h[k][ini-1]*pot[k][fim-ini+1];
	val%=MOD;
	val=h[k][fim]-val; val%=MOD;
	val+=MOD; val%=MOD;
	return val;
}
 
ll junta(ll a, ll b, int tam, int k) {
	if(tam==0) return a;
	ll val=a*pot[k][tam];
	val%=MOD;
	val+=b;
	return val%MOD;
}
 
bool checa(int k) {
	vector<int> aux;
	for(int i=1; i<=n; i++) if(i!=k) aux.push_back(v[i]);
	for(int i=0; i<n/2; i++) {
		printf("%c", aux[i]);
		if(aux[i]!=aux[i+n/2]) assert(0);
	}
	return 1;
}
 
int main() {
	scanf("%d", &n);
	scanf(" %s", &v[1]);
 
	if(n%2==0) {
		printf("NOT POSSIBLE\n");
		return 0;
	}
 
	pot[0][0]=1; pot[1][0]=1;
	for(int i=1; i<=n; i++) {
		h[0][i]=h[0][i-1]*P; h[0][i]%=MOD;
		h[0][i]+=(v[i]-'A'+1); h[0][i]%=MOD;
		h[1][i]=h[1][i-1]*P2; h[1][i]%=MOD;
		h[1][i]+=(v[i]-'A'+1); h[1][i]%=MOD;
 
		pot[0][i]=pot[0][i-1]*P; pot[0][i]%=MOD;
		pot[1][i]=pot[1][i-1]*P2; pot[1][i]%=MOD;
	}
 
	// for(int i=1; i<=n; i++) printf("%d ", pot[i]); printf("\n");
	// printf("ghs %lld %lld %lld >> %lld\n", gh(1, 2, 0), gh(2, 3, 0), gh(2, 5, 0), junta(gh(1, 2, 0), gh(2, 3, 0), 2, 0));
 
	int resp=-1;
	for(int i=1; i<=n; i++) {
		// printf("testando %d\n", i);
		ll aa, bb; ll aa2, bb2;
		if(i<=(n+1)/2) {
			aa=junta( gh(1, i-1, 0), gh(i+1, n/2+1, 0), n/2-i+1, 0);
			bb=gh(n/2+2, n, 0);
			aa2=junta( gh(1, i-1, 1), gh(i+1, n/2+1, 1), n/2-i+1, 1);
			bb2=gh(n/2+2, n, 1);
			// printf("[%d %d] [%d %d] (%d) // [%d %d] >> ", 1, i-1, i+1, (n+1)/2, n/2-i+1, (n+1)/2+1, n);
			// printf("%lld %lld\n", aa, bb);
		}
		else {
			aa=gh(1, n/2, 0);
			bb=junta( gh(n/2+1, i-1, 0) , gh(i+1, n, 0), n-i, 0);
			aa2=gh(1, n/2, 1);
			bb2=junta( gh(n/2+1, i-1, 1) , gh(i+1, n, 1), n-i, 1);
			// printf("[%d %d] // [%d %d] [%d %d] (%d) >> ", 1, n/2, (n+1)/2, i-1, i+1, n, n-i);
			// printf("%lld %lld\n", aa, bb);
		}
 
		if(aa==bb&&aa2==bb2) {
			s.insert(aa2);
			//printf("%d inserindo %lld\n", i, aa);
			if(s.size()>1) {
				printf("NOT UNIQUE\n");
				return 0;
			}
          	resp=i;
		}
	}
 
	if(resp==-1) {
		printf("NOT POSSIBLE\n");
		return 0;
	}
 
	checa(resp);
}

Compilation message

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

Subtask #1
35.0 / 35.0

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

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 73828 KB Output is correct
2 Correct 293 ms 73780 KB Output is correct
3 Correct 342 ms 73940 KB Output is correct
4 Correct 241 ms 73808 KB Output is correct
5 Correct 278 ms 73808 KB Output is correct
6 Correct 10 ms 4224 KB Output is correct
7 Correct 308 ms 75900 KB Output is correct
8 Correct 178 ms 60280 KB Output is correct
9 Correct 307 ms 68808 KB Output is correct
10 Correct 236 ms 68580 KB Output is correct
11 Correct 167 ms 55800 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 2 ms 384 KB Output is correct
34 Correct 2 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 2 ms 512 KB Output is correct
37 Correct 2 ms 256 KB Output is correct
38 Correct 2 ms 384 KB Output is correct
39 Correct 2 ms 384 KB Output is correct
40 Correct 2 ms 384 KB Output is correct
41 Correct 2 ms 384 KB Output is correct
42 Correct 2 ms 384 KB Output is correct
43 Correct 2 ms 384 KB Output is correct
44 Correct 2 ms 384 KB Output is correct
45 Correct 0 ms 384 KB Output is correct
46 Correct 2 ms 384 KB Output is correct
47 Correct 2 ms 384 KB Output is correct
48 Correct 2 ms 384 KB Output is correct
49 Correct 2 ms 384 KB Output is correct
50 Correct 2 ms 384 KB Output is correct
51 Correct 2 ms 384 KB Output is correct
52 Correct 2 ms 384 KB Output is correct
53 Correct 2 ms 384 KB Output is correct
54 Correct 2 ms 384 KB Output is correct