oj.uz

Submission #127558

# Submission time Handle Problem Language Result Execution time Memory
127558 2019-07-09T14:58:30 Z mechfrog88 Genetics (BOI18_genetics) C++14
27 / 100
 28 ms 3832 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,m,k;
	cin >> n >> m >> k;
	vector <string> arr(n);
	bitset<4101> s[n];
	for (int z=0;z<n;z++){
		cin >> arr[z];
		for (int x=0;x<m;x++){
			if (arr[z][x] == 'A') s[z][x] = 1;
			else s[z][x] = 0;
		}
	}
	if (n <= 100){
		for (int z=0;z<n;z++){
			bool ok = true;
			for (int x=0;x<n;x++){
				if (z == x) continue;
				ll c = 0;
				for (int q=0;q<m;q++){
					if (arr[z][q] != arr[x][q]) c++;
				}
				if (c != k){
					ok = false;
					break;
				}
			}
			if (ok){
				cout << z+1 << endl;
				return 0;
			}
		}
	} else {
		vector <bool> cannot(n,false);
		for (int z=0;z<n;z++){
			bool ok = true;
			if (cannot[z]) continue;
			for (int x=0;x<n;x++){
				if (cannot[x]) continue;
				if (z == x) continue;
				bitset <4101> temp;
				temp = s[z]^s[x];
				ll c = temp.count();
				if (c != k){
					cannot[x] = true;
					cannot[z] = true;
					ok = false;
					break;
				}
			}
			if (ok){
				cout << z+1 << endl;
				return 0;
			}
		}
	}
	
}

Subtask #1
27.0 / 27.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 3832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 3832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Incorrect 28 ms 3832 KB Output isn't correct
19 Halted 0 ms 0 KB -