oj.uz

Submission #895652

# Submission time Handle Problem Language Result Execution time Memory
895652 2023-12-30T13:02:50 Z pcc Genetics (BOI18_genetics) C++14
46 / 100
 2000 ms 60244 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 4140;
int arr[mxn][mxn];
int N,M,K;
vector<int> v,cand;
const int magic = 5;
bitset<mxn> in;
const int lim = 1.95*CLOCKS_PER_SEC;
int st;

int dif(int a,int b){
	int re = 0;
	for(int i = 0;i<M;i++){
		re += (arr[a][i] != arr[b][i]);
	}
	return re;
}

void collect(){
	for(int i = 0;i<N;i++){
		for(int j = i+1;j<N;j++){
			if(dif(i,j) != K){
				if(!in[i])v.push_back(i);
				if(!in[j])v.push_back(j);
				in[i] = in[j] = true;
			}
		}
		if(!in[i]){
			cout<<i+1;
			exit(0);
		}
	}
	return;
}

int main(){
	st = clock();
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>K;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<M;j++){
			char c;
			cin>>c;
			arr[i][j] = c-'A';
		}
	}
	collect();
	for(int i = 0;i<N;i++){
		if(in[i])continue;
		bool flag = true;
		for(auto &j:v){
			if(dif(i,j) != K)flag = false;
		}
		if(flag)cand.push_back(i);
	}
	assert(cand.size()<100);
	for(auto &i:cand){
		bool flag = true;
		for(int j = 0;j<N;j++){
			if(i == j)continue;
			if(dif(i,j) != K){
				flag = false;
				break;
			}
		}
		if(flag){
			cout<<i+1;
			return 0;
		}
	}
	assert(false);
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2488 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2552 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 25180 KB Output is correct
2 Correct 422 ms 31576 KB Output is correct
3 Correct 336 ms 29304 KB Output is correct
4 Correct 52 ms 18780 KB Output is correct
5 Correct 160 ms 31356 KB Output is correct
6 Correct 300 ms 31364 KB Output is correct
7 Correct 69 ms 12892 KB Output is correct
8 Correct 63 ms 12888 KB Output is correct
9 Correct 46 ms 29264 KB Output is correct
10 Correct 386 ms 29300 KB Output is correct
11 Correct 203 ms 25208 KB Output is correct
12 Correct 47 ms 25180 KB Output is correct
13 Correct 121 ms 25172 KB Output is correct
14 Correct 169 ms 23128 KB Output is correct
15 Correct 71 ms 23124 KB Output is correct
16 Correct 122 ms 25200 KB Output is correct
17 Correct 323 ms 29268 KB Output is correct
18 Correct 68 ms 29264 KB Output is correct
19 Correct 320 ms 29304 KB Output is correct
20 Correct 181 ms 29540 KB Output is correct
21 Correct 298 ms 29304 KB Output is correct
22 Correct 344 ms 29312 KB Output is correct
23 Correct 333 ms 29308 KB Output is correct
24 Correct 401 ms 29312 KB Output is correct
25 Correct 248 ms 29308 KB Output is correct
26 Correct 314 ms 29300 KB Output is correct
27 Correct 293 ms 29300 KB Output is correct
28 Correct 228 ms 29292 KB Output is correct
29 Correct 406 ms 29292 KB Output is correct
30 Correct 238 ms 31300 KB Output is correct
31 Correct 399 ms 31360 KB Output is correct
32 Correct 393 ms 31316 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 2392 KB Output is correct
35 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 25180 KB Output is correct
2 Correct 422 ms 31576 KB Output is correct
3 Correct 336 ms 29304 KB Output is correct
4 Correct 52 ms 18780 KB Output is correct
5 Correct 160 ms 31356 KB Output is correct
6 Correct 300 ms 31364 KB Output is correct
7 Correct 69 ms 12892 KB Output is correct
8 Correct 63 ms 12888 KB Output is correct
9 Correct 46 ms 29264 KB Output is correct
10 Correct 386 ms 29300 KB Output is correct
11 Correct 203 ms 25208 KB Output is correct
12 Correct 47 ms 25180 KB Output is correct
13 Correct 121 ms 25172 KB Output is correct
14 Correct 169 ms 23128 KB Output is correct
15 Correct 71 ms 23124 KB Output is correct
16 Correct 122 ms 25200 KB Output is correct
17 Correct 323 ms 29268 KB Output is correct
18 Correct 68 ms 29264 KB Output is correct
19 Correct 320 ms 29304 KB Output is correct
20 Correct 181 ms 29540 KB Output is correct
21 Correct 298 ms 29304 KB Output is correct
22 Correct 344 ms 29312 KB Output is correct
23 Correct 333 ms 29308 KB Output is correct
24 Correct 401 ms 29312 KB Output is correct
25 Correct 248 ms 29308 KB Output is correct
26 Correct 314 ms 29300 KB Output is correct
27 Correct 293 ms 29300 KB Output is correct
28 Correct 228 ms 29292 KB Output is correct
29 Correct 406 ms 29292 KB Output is correct
30 Correct 238 ms 31300 KB Output is correct
31 Correct 399 ms 31360 KB Output is correct
32 Correct 393 ms 31316 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 2392 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Execution timed out 2029 ms 60244 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2488 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2552 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 237 ms 25180 KB Output is correct
19 Correct 422 ms 31576 KB Output is correct
20 Correct 336 ms 29304 KB Output is correct
21 Correct 52 ms 18780 KB Output is correct
22 Correct 160 ms 31356 KB Output is correct
23 Correct 300 ms 31364 KB Output is correct
24 Correct 69 ms 12892 KB Output is correct
25 Correct 63 ms 12888 KB Output is correct
26 Correct 46 ms 29264 KB Output is correct
27 Correct 386 ms 29300 KB Output is correct
28 Correct 203 ms 25208 KB Output is correct
29 Correct 47 ms 25180 KB Output is correct
30 Correct 121 ms 25172 KB Output is correct
31 Correct 169 ms 23128 KB Output is correct
32 Correct 71 ms 23124 KB Output is correct
33 Correct 122 ms 25200 KB Output is correct
34 Correct 323 ms 29268 KB Output is correct
35 Correct 68 ms 29264 KB Output is correct
36 Correct 320 ms 29304 KB Output is correct
37 Correct 181 ms 29540 KB Output is correct
38 Correct 298 ms 29304 KB Output is correct
39 Correct 344 ms 29312 KB Output is correct
40 Correct 333 ms 29308 KB Output is correct
41 Correct 401 ms 29312 KB Output is correct
42 Correct 248 ms 29308 KB Output is correct
43 Correct 314 ms 29300 KB Output is correct
44 Correct 293 ms 29300 KB Output is correct
45 Correct 228 ms 29292 KB Output is correct
46 Correct 406 ms 29292 KB Output is correct
47 Correct 238 ms 31300 KB Output is correct
48 Correct 399 ms 31360 KB Output is correct
49 Correct 393 ms 31316 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 1 ms 2392 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Execution timed out 2029 ms 60244 KB Time limit exceeded
54 Halted 0 ms 0 KB -