oj.uz

답안 #307089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
307089 2020-09-27T02:04:14 Z Rainbowbunny Genetics (BOI18_genetics) C++17
100 / 100
 905 ms 148900 KB 
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using cd = complex <double>;
 
typedef pair <int, int> pii;
const int N = 3e3 + 5;
const long long INF = 1e18;
const int mod = 1e9 + 123;//786433;//998244353;
const double Pi = acos(-1);
const int p = 510200;
 
void Fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}
 
int n, m, k;
int a[4105][4105];
int x[4105];
int f[4105][4];
 
signed main()
{
	Fastio();
	cin >> n >> m >> k;
	x[0] = 1;
	for(int i = 1; i < n; i++)
	{
		x[i] = 1ll * x[i - 1] * p % mod;
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			char temp;
			cin >> temp;
			if(temp == 'A')
			{
				a[i][j] = 0;
			}
			else if(temp == 'T')
			{
				a[i][j] = 1;
			}
			else if(temp == 'G')
			{
				a[i][j] = 2;
			}
			else
			{
				a[i][j] = 3;
			}
			f[j][a[i][j]] += x[i];
			f[j][a[i][j]] %= mod;
		}
	}
	for(int i = 0; i < n; i++)
	{
		int temp = 0, cur = 0;
		for(int j = 0; j < m; j++)
		{
			for(int t = 0; t < 4; t++)
			{
				if(t != a[i][j])
				{
					temp = temp + f[j][t];
					temp = (temp + mod) % mod;
				}
			}
		}
		for(int j = 0; j < n; j++)
		{
			if(j != i)
			{
				int r = 1ll * (x[j] * k) % mod;
				cur = (cur % mod + r + mod) % mod; 
			}
		}
		if(temp == cur)
		{
			cout << i + 1;
			return 0;
		}
	}
}

Subtask #1
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 2 ms 896 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 768 KB Output is correct
12 Correct 1 ms 768 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 1 ms 896 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 1 ms 768 KB Output is correct
17 Correct 1 ms 384 KB Output is correct

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 29432 KB Output is correct
2 Correct 144 ms 36088 KB Output is correct
3 Correct 159 ms 34552 KB Output is correct
4 Correct 39 ms 10880 KB Output is correct
5 Correct 100 ms 36088 KB Output is correct
6 Correct 120 ms 36088 KB Output is correct
7 Correct 63 ms 15608 KB Output is correct
8 Correct 60 ms 15608 KB Output is correct
9 Correct 90 ms 33656 KB Output is correct
10 Correct 136 ms 33656 KB Output is correct
11 Correct 111 ms 29548 KB Output is correct
12 Correct 81 ms 29688 KB Output is correct
13 Correct 92 ms 29544 KB Output is correct
14 Correct 108 ms 25336 KB Output is correct
15 Correct 75 ms 25720 KB Output is correct
16 Correct 83 ms 26232 KB Output is correct
17 Correct 143 ms 34680 KB Output is correct
18 Correct 93 ms 34424 KB Output is correct
19 Correct 136 ms 34680 KB Output is correct
20 Correct 102 ms 34424 KB Output is correct
21 Correct 134 ms 34552 KB Output is correct
22 Correct 153 ms 34424 KB Output is correct
23 Correct 158 ms 34516 KB Output is correct
24 Correct 154 ms 34536 KB Output is correct
25 Correct 107 ms 34424 KB Output is correct
26 Correct 121 ms 34552 KB Output is correct
27 Correct 115 ms 34304 KB Output is correct
28 Correct 115 ms 34296 KB Output is correct
29 Correct 140 ms 34424 KB Output is correct
30 Correct 109 ms 36344 KB Output is correct
31 Correct 137 ms 36088 KB Output is correct
32 Correct 114 ms 36216 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 768 KB Output is correct
35 Correct 1 ms 384 KB Output is correct

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 29432 KB Output is correct
2 Correct 144 ms 36088 KB Output is correct
3 Correct 159 ms 34552 KB Output is correct
4 Correct 39 ms 10880 KB Output is correct
5 Correct 100 ms 36088 KB Output is correct
6 Correct 120 ms 36088 KB Output is correct
7 Correct 63 ms 15608 KB Output is correct
8 Correct 60 ms 15608 KB Output is correct
9 Correct 90 ms 33656 KB Output is correct
10 Correct 136 ms 33656 KB Output is correct
11 Correct 111 ms 29548 KB Output is correct
12 Correct 81 ms 29688 KB Output is correct
13 Correct 92 ms 29544 KB Output is correct
14 Correct 108 ms 25336 KB Output is correct
15 Correct 75 ms 25720 KB Output is correct
16 Correct 83 ms 26232 KB Output is correct
17 Correct 143 ms 34680 KB Output is correct
18 Correct 93 ms 34424 KB Output is correct
19 Correct 136 ms 34680 KB Output is correct
20 Correct 102 ms 34424 KB Output is correct
21 Correct 134 ms 34552 KB Output is correct
22 Correct 153 ms 34424 KB Output is correct
23 Correct 158 ms 34516 KB Output is correct
24 Correct 154 ms 34536 KB Output is correct
25 Correct 107 ms 34424 KB Output is correct
26 Correct 121 ms 34552 KB Output is correct
27 Correct 115 ms 34304 KB Output is correct
28 Correct 115 ms 34296 KB Output is correct
29 Correct 140 ms 34424 KB Output is correct
30 Correct 109 ms 36344 KB Output is correct
31 Correct 137 ms 36088 KB Output is correct
32 Correct 114 ms 36216 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 768 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 571 ms 130168 KB Output is correct
37 Correct 593 ms 148728 KB Output is correct
38 Correct 803 ms 145272 KB Output is correct
39 Correct 248 ms 66936 KB Output is correct
40 Correct 694 ms 148728 KB Output is correct
41 Correct 333 ms 74488 KB Output is correct
42 Correct 293 ms 74488 KB Output is correct
43 Correct 394 ms 119416 KB Output is correct
44 Correct 507 ms 148600 KB Output is correct
45 Correct 704 ms 148640 KB Output is correct
46 Correct 496 ms 148600 KB Output is correct
47 Correct 588 ms 130208 KB Output is correct
48 Correct 674 ms 130296 KB Output is correct
49 Correct 395 ms 111608 KB Output is correct
50 Correct 554 ms 111608 KB Output is correct
51 Correct 597 ms 125560 KB Output is correct
52 Correct 740 ms 145144 KB Output is correct
53 Correct 760 ms 145016 KB Output is correct
54 Correct 498 ms 144760 KB Output is correct
55 Correct 723 ms 144760 KB Output is correct
56 Correct 488 ms 144856 KB Output is correct
57 Correct 811 ms 145400 KB Output is correct
58 Correct 629 ms 145496 KB Output is correct
59 Correct 548 ms 144632 KB Output is correct
60 Correct 529 ms 145528 KB Output is correct
61 Correct 543 ms 144564 KB Output is correct
62 Correct 512 ms 144248 KB Output is correct
63 Correct 489 ms 145272 KB Output is correct
64 Correct 520 ms 145144 KB Output is correct
65 Correct 741 ms 144760 KB Output is correct
66 Correct 711 ms 145048 KB Output is correct
67 Correct 697 ms 145528 KB Output is correct
68 Correct 622 ms 145516 KB Output is correct
69 Correct 463 ms 144632 KB Output is correct
70 Correct 702 ms 145144 KB Output is correct
71 Correct 601 ms 144800 KB Output is correct
72 Correct 628 ms 145656 KB Output is correct
73 Correct 682 ms 144888 KB Output is correct
74 Correct 1 ms 384 KB Output is correct
75 Correct 1 ms 768 KB Output is correct
76 Correct 1 ms 384 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 2 ms 896 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 768 KB Output is correct
12 Correct 1 ms 768 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 1 ms 896 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 1 ms 768 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 132 ms 29432 KB Output is correct
19 Correct 144 ms 36088 KB Output is correct
20 Correct 159 ms 34552 KB Output is correct
21 Correct 39 ms 10880 KB Output is correct
22 Correct 100 ms 36088 KB Output is correct
23 Correct 120 ms 36088 KB Output is correct
24 Correct 63 ms 15608 KB Output is correct
25 Correct 60 ms 15608 KB Output is correct
26 Correct 90 ms 33656 KB Output is correct
27 Correct 136 ms 33656 KB Output is correct
28 Correct 111 ms 29548 KB Output is correct
29 Correct 81 ms 29688 KB Output is correct
30 Correct 92 ms 29544 KB Output is correct
31 Correct 108 ms 25336 KB Output is correct
32 Correct 75 ms 25720 KB Output is correct
33 Correct 83 ms 26232 KB Output is correct
34 Correct 143 ms 34680 KB Output is correct
35 Correct 93 ms 34424 KB Output is correct
36 Correct 136 ms 34680 KB Output is correct
37 Correct 102 ms 34424 KB Output is correct
38 Correct 134 ms 34552 KB Output is correct
39 Correct 153 ms 34424 KB Output is correct
40 Correct 158 ms 34516 KB Output is correct
41 Correct 154 ms 34536 KB Output is correct
42 Correct 107 ms 34424 KB Output is correct
43 Correct 121 ms 34552 KB Output is correct
44 Correct 115 ms 34304 KB Output is correct
45 Correct 115 ms 34296 KB Output is correct
46 Correct 140 ms 34424 KB Output is correct
47 Correct 109 ms 36344 KB Output is correct
48 Correct 137 ms 36088 KB Output is correct
49 Correct 114 ms 36216 KB Output is correct
50 Correct 1 ms 384 KB Output is correct
51 Correct 1 ms 768 KB Output is correct
52 Correct 1 ms 384 KB Output is correct
53 Correct 571 ms 130168 KB Output is correct
54 Correct 593 ms 148728 KB Output is correct
55 Correct 803 ms 145272 KB Output is correct
56 Correct 248 ms 66936 KB Output is correct
57 Correct 694 ms 148728 KB Output is correct
58 Correct 333 ms 74488 KB Output is correct
59 Correct 293 ms 74488 KB Output is correct
60 Correct 394 ms 119416 KB Output is correct
61 Correct 507 ms 148600 KB Output is correct
62 Correct 704 ms 148640 KB Output is correct
63 Correct 496 ms 148600 KB Output is correct
64 Correct 588 ms 130208 KB Output is correct
65 Correct 674 ms 130296 KB Output is correct
66 Correct 395 ms 111608 KB Output is correct
67 Correct 554 ms 111608 KB Output is correct
68 Correct 597 ms 125560 KB Output is correct
69 Correct 740 ms 145144 KB Output is correct
70 Correct 760 ms 145016 KB Output is correct
71 Correct 498 ms 144760 KB Output is correct
72 Correct 723 ms 144760 KB Output is correct
73 Correct 488 ms 144856 KB Output is correct
74 Correct 811 ms 145400 KB Output is correct
75 Correct 629 ms 145496 KB Output is correct
76 Correct 548 ms 144632 KB Output is correct
77 Correct 529 ms 145528 KB Output is correct
78 Correct 543 ms 144564 KB Output is correct
79 Correct 512 ms 144248 KB Output is correct
80 Correct 489 ms 145272 KB Output is correct
81 Correct 520 ms 145144 KB Output is correct
82 Correct 741 ms 144760 KB Output is correct
83 Correct 711 ms 145048 KB Output is correct
84 Correct 697 ms 145528 KB Output is correct
85 Correct 622 ms 145516 KB Output is correct
86 Correct 463 ms 144632 KB Output is correct
87 Correct 702 ms 145144 KB Output is correct
88 Correct 601 ms 144800 KB Output is correct
89 Correct 628 ms 145656 KB Output is correct
90 Correct 682 ms 144888 KB Output is correct
91 Correct 1 ms 384 KB Output is correct
92 Correct 1 ms 768 KB Output is correct
93 Correct 1 ms 384 KB Output is correct
94 Correct 513 ms 140800 KB Output is correct
95 Correct 736 ms 148728 KB Output is correct
96 Correct 885 ms 146168 KB Output is correct
97 Correct 444 ms 79608 KB Output is correct
98 Correct 291 ms 66936 KB Output is correct
99 Correct 740 ms 148600 KB Output is correct
100 Correct 363 ms 74620 KB Output is correct
101 Correct 322 ms 74824 KB Output is correct
102 Correct 419 ms 119544 KB Output is correct
103 Correct 592 ms 148900 KB Output is correct
104 Correct 809 ms 148600 KB Output is correct
105 Correct 905 ms 148860 KB Output is correct
106 Correct 786 ms 141304 KB Output is correct
107 Correct 472 ms 130168 KB Output is correct
108 Correct 503 ms 111612 KB Output is correct
109 Correct 623 ms 128236 KB Output is correct
110 Correct 695 ms 125304 KB Output is correct
111 Correct 564 ms 148856 KB Output is correct
112 Correct 740 ms 146808 KB Output is correct
113 Correct 806 ms 144760 KB Output is correct
114 Correct 480 ms 145088 KB Output is correct
115 Correct 771 ms 144888 KB Output is correct
116 Correct 802 ms 146680 KB Output is correct
117 Correct 761 ms 146936 KB Output is correct
118 Correct 738 ms 146680 KB Output is correct
119 Correct 667 ms 146380 KB Output is correct
120 Correct 788 ms 146960 KB Output is correct
121 Correct 560 ms 130040 KB Output is correct
122 Correct 584 ms 148728 KB Output is correct
123 Correct 806 ms 145272 KB Output is correct
124 Correct 1 ms 384 KB Output is correct
125 Correct 1 ms 896 KB Output is correct
126 Correct 1 ms 384 KB Output is correct