oj.uz

Submission #162805

# Submission time Handle Problem Language Result Execution time Memory
162805 2019-11-09T19:36:18 Z faremy Genetics (BOI18_genetics) C++14
46 / 100
 2000 ms 576120 KB 
#include <iostream>
#include <algorithm>
#include <cstdlib>


const int MAXN = 4100;
const int MAXT = 16400;
const long long MOD = 1e14;

long long dna[MAXN][MAXT];
long long unify[MAXN][MAXN];

long long randomVector[MAXN];
long long randDna[MAXT];
long long randDiff[MAXN];
long long randUnify[MAXN];


int search(int sequences, int size)
{
	for (int iSeq = 0; iSeq < sequences; iSeq++)
		randomVector[iSeq] = (rand() * rand() * rand() * rand()) % MOD;

	for (int iChar = 0; iChar < size; iChar++)
	{
		randDna[iChar] = 0;
		for (int iSeq = 0; iSeq < sequences; iSeq++)
			randDna[iChar] = (randDna[iChar] + dna[iSeq][iChar] * randomVector[iSeq]) % MOD;
	}

	for (int iSeq = 0; iSeq < sequences; iSeq++)
	{
		randDiff[iSeq] = 0;
		for (int iChar = 0; iChar < size; iChar++)
			randDiff[iSeq] = (randDiff[iSeq] + dna[iSeq][iChar] * randDna[iChar]) % MOD;
	}

	for (int iSeq = 0; iSeq < sequences; iSeq++)
	{
		randUnify[iSeq] = 0;
		for (int jSeq = 0; jSeq < sequences; jSeq++)
			randUnify[iSeq] = (randUnify[iSeq] + unify[iSeq][jSeq] * randomVector[jSeq]) % MOD;
	}

	int answer = -1;
	for (int iSeq = 0; iSeq < sequences; iSeq++)
		if (randDiff[iSeq] == randUnify[iSeq])
		{
			if (answer == -1)
				answer = iSeq;
			else
				return -1;
		}

	return answer;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int sequences, size, differences;
	std::cin >> sequences >> size >> differences;

	for (int iSeq = 0; iSeq < sequences; iSeq++)
		for (int iChar = 0; iChar < size; iChar++)
		{
			char elem; std::cin >> elem;
			for (int iTrs = 0; iTrs < 4; iTrs++)
				dna[iSeq][4 * iChar + iTrs] = -1;

			switch (elem)
			{
			case 'A':
				dna[iSeq][4 * iChar] = 1;
				break;
			case 'G':
				dna[iSeq][4 * iChar + 1] = 1;
				break;
			case 'C':
				dna[iSeq][4 * iChar + 2] = 1;
				break;
			case 'T':
				dna[iSeq][4 * iChar + 3] = 1;
				break;
			}
		}

	for (int iSeq = 0; iSeq < sequences; iSeq++)
	{
		for (int jSeq = 0; jSeq < sequences; jSeq++)
			unify[iSeq][jSeq] = 4 * (size - differences);
		unify[iSeq][iSeq] = 4 * size;
	}

	srand(42);
	int answer = search(sequences, 4 * size);

	while (answer == -1)
		answer = search(sequences, 4 * size);
	std::cout << answer + 1 << '\n';

	return 0;
}

Subtask #1
27.0 / 27.0

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 112888 KB Output is correct
2 Correct 431 ms 142072 KB Output is correct
3 Correct 415 ms 134648 KB Output is correct
4 Correct 82 ms 41080 KB Output is correct
5 Correct 438 ms 142072 KB Output is correct
6 Correct 435 ms 142072 KB Output is correct
7 Correct 116 ms 54648 KB Output is correct
8 Correct 172 ms 54648 KB Output is correct
9 Correct 399 ms 131576 KB Output is correct
10 Correct 401 ms 131652 KB Output is correct
11 Correct 544 ms 112760 KB Output is correct
12 Correct 555 ms 113528 KB Output is correct
13 Correct 541 ms 112888 KB Output is correct
14 Correct 423 ms 94456 KB Output is correct
15 Correct 434 ms 95968 KB Output is correct
16 Correct 460 ms 100216 KB Output is correct
17 Correct 409 ms 135040 KB Output is correct
18 Correct 420 ms 133744 KB Output is correct
19 Correct 420 ms 135224 KB Output is correct
20 Correct 406 ms 132988 KB Output is correct
21 Correct 414 ms 134652 KB Output is correct
22 Correct 419 ms 133404 KB Output is correct
23 Correct 407 ms 134136 KB Output is correct
24 Correct 409 ms 134136 KB Output is correct
25 Correct 401 ms 132984 KB Output is correct
26 Correct 416 ms 134392 KB Output is correct
27 Correct 416 ms 133244 KB Output is correct
28 Correct 416 ms 133240 KB Output is correct
29 Correct 406 ms 134264 KB Output is correct
30 Correct 435 ms 142200 KB Output is correct
31 Correct 443 ms 142328 KB Output is correct
32 Correct 448 ms 142200 KB Output is correct
33 Correct 5 ms 504 KB Output is correct
34 Correct 6 ms 1528 KB Output is correct
35 Correct 5 ms 504 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 112888 KB Output is correct
2 Correct 431 ms 142072 KB Output is correct
3 Correct 415 ms 134648 KB Output is correct
4 Correct 82 ms 41080 KB Output is correct
5 Correct 438 ms 142072 KB Output is correct
6 Correct 435 ms 142072 KB Output is correct
7 Correct 116 ms 54648 KB Output is correct
8 Correct 172 ms 54648 KB Output is correct
9 Correct 399 ms 131576 KB Output is correct
10 Correct 401 ms 131652 KB Output is correct
11 Correct 544 ms 112760 KB Output is correct
12 Correct 555 ms 113528 KB Output is correct
13 Correct 541 ms 112888 KB Output is correct
14 Correct 423 ms 94456 KB Output is correct
15 Correct 434 ms 95968 KB Output is correct
16 Correct 460 ms 100216 KB Output is correct
17 Correct 409 ms 135040 KB Output is correct
18 Correct 420 ms 133744 KB Output is correct
19 Correct 420 ms 135224 KB Output is correct
20 Correct 406 ms 132988 KB Output is correct
21 Correct 414 ms 134652 KB Output is correct
22 Correct 419 ms 133404 KB Output is correct
23 Correct 407 ms 134136 KB Output is correct
24 Correct 409 ms 134136 KB Output is correct
25 Correct 401 ms 132984 KB Output is correct
26 Correct 416 ms 134392 KB Output is correct
27 Correct 416 ms 133244 KB Output is correct
28 Correct 416 ms 133240 KB Output is correct
29 Correct 406 ms 134264 KB Output is correct
30 Correct 435 ms 142200 KB Output is correct
31 Correct 443 ms 142328 KB Output is correct
32 Correct 448 ms 142200 KB Output is correct
33 Correct 5 ms 504 KB Output is correct
34 Correct 6 ms 1528 KB Output is correct
35 Correct 5 ms 504 KB Output is correct
36 Execution timed out 2127 ms 576120 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1400 KB Output is correct
2 Correct 6 ms 1528 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 6 ms 1144 KB Output is correct
5 Correct 6 ms 1272 KB Output is correct
6 Correct 6 ms 1528 KB Output is correct
7 Correct 5 ms 888 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 ms 1016 KB Output is correct
10 Correct 6 ms 1528 KB Output is correct
11 Correct 6 ms 1272 KB Output is correct
12 Correct 6 ms 1528 KB Output is correct
13 Correct 6 ms 1528 KB Output is correct
14 Correct 6 ms 1528 KB Output is correct
15 Correct 6 ms 1528 KB Output is correct
16 Correct 5 ms 1272 KB Output is correct
17 Correct 5 ms 504 KB Output is correct
18 Correct 541 ms 112888 KB Output is correct
19 Correct 431 ms 142072 KB Output is correct
20 Correct 415 ms 134648 KB Output is correct
21 Correct 82 ms 41080 KB Output is correct
22 Correct 438 ms 142072 KB Output is correct
23 Correct 435 ms 142072 KB Output is correct
24 Correct 116 ms 54648 KB Output is correct
25 Correct 172 ms 54648 KB Output is correct
26 Correct 399 ms 131576 KB Output is correct
27 Correct 401 ms 131652 KB Output is correct
28 Correct 544 ms 112760 KB Output is correct
29 Correct 555 ms 113528 KB Output is correct
30 Correct 541 ms 112888 KB Output is correct
31 Correct 423 ms 94456 KB Output is correct
32 Correct 434 ms 95968 KB Output is correct
33 Correct 460 ms 100216 KB Output is correct
34 Correct 409 ms 135040 KB Output is correct
35 Correct 420 ms 133744 KB Output is correct
36 Correct 420 ms 135224 KB Output is correct
37 Correct 406 ms 132988 KB Output is correct
38 Correct 414 ms 134652 KB Output is correct
39 Correct 419 ms 133404 KB Output is correct
40 Correct 407 ms 134136 KB Output is correct
41 Correct 409 ms 134136 KB Output is correct
42 Correct 401 ms 132984 KB Output is correct
43 Correct 416 ms 134392 KB Output is correct
44 Correct 416 ms 133244 KB Output is correct
45 Correct 416 ms 133240 KB Output is correct
46 Correct 406 ms 134264 KB Output is correct
47 Correct 435 ms 142200 KB Output is correct
48 Correct 443 ms 142328 KB Output is correct
49 Correct 448 ms 142200 KB Output is correct
50 Correct 5 ms 504 KB Output is correct
51 Correct 6 ms 1528 KB Output is correct
52 Correct 5 ms 504 KB Output is correct
53 Execution timed out 2127 ms 576120 KB Time limit exceeded
54 Halted 0 ms 0 KB -