oj.uz

답안 #895655

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895655 2023-12-30T13:05:20 Z pcc Genetics (BOI18_genetics) C++14
27 / 100
 71 ms 63256 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 = 20;
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);
				if(v.size()>=magic)return;
				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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 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 2396 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 2396 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 25176 KB Output is correct
2 Runtime error 71 ms 63256 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 25176 KB Output is correct
2 Runtime error 71 ms 63256 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 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 2396 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 2396 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 39 ms 25176 KB Output is correct
19 Runtime error 71 ms 63256 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -