# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
117493 | 2019-06-16T08:54:57 Z | ckodser | Genetics (BOI18_genetics) | C++14 | 1256 ms | 24356 KB |
#include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);} #define ll int #define pb push_back #define ld long double #define mp make_pair #define F first #define S second #define pii pair<ll,ll> using namespace :: std; const ll maxn=4110; const ll maxg=30; string s[maxn]; bool hast[maxg][maxn]; ll sz[maxg]; ll cnt[maxg][maxn][4]; ll n,m,k; bool canBeAns(ll i){ for(ll y=0;y<maxg;y++){ ll ans=0; ll szz=sz[y]; for(ll j=0;j<m;j++){ ans+=cnt[y][j][s[i][j]]; } if(hast[y][i]){ ans-=m; szz--; } if(ans!=szz*(m-k)){ return 0; } } return 1; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m>>k; for(ll i=0;i<n;i++){ cin>>s[i]; } for(ll i=0;i<n;i++){ for(ll j=0;j<m;j++){ if(s[i][j]=='A')s[i][j]=0; if(s[i][j]=='C')s[i][j]=1; if(s[i][j]=='T')s[i][j]=2; if(s[i][j]=='G')s[i][j]=3; } for(ll y=0;y<maxg;y++){ if(rand()%2==0){ hast[y][i]=1; sz[y]++; for(ll j=0;j<m;j++){ cnt[y][j][s[i][j]]++; } } } } for(ll i=0;i<n;i++){ if(canBeAns(i)){ cout<<i+1; return 0; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 760 KB | Output is correct |
2 | Correct | 6 ms | 764 KB | Output is correct |
3 | Correct | 6 ms | 760 KB | Output is correct |
4 | Correct | 5 ms | 760 KB | Output is correct |
5 | Correct | 5 ms | 760 KB | Output is correct |
6 | Correct | 6 ms | 760 KB | Output is correct |
7 | Correct | 5 ms | 760 KB | Output is correct |
8 | Correct | 5 ms | 760 KB | Output is correct |
9 | Correct | 5 ms | 760 KB | Output is correct |
10 | Correct | 5 ms | 760 KB | Output is correct |
11 | Correct | 6 ms | 888 KB | Output is correct |
12 | Correct | 6 ms | 760 KB | Output is correct |
13 | Correct | 6 ms | 760 KB | Output is correct |
14 | Correct | 6 ms | 760 KB | Output is correct |
15 | Correct | 6 ms | 760 KB | Output is correct |
16 | Correct | 5 ms | 760 KB | Output is correct |
17 | Correct | 5 ms | 760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 202 ms | 4348 KB | Output is correct |
2 | Correct | 225 ms | 5112 KB | Output is correct |
3 | Correct | 227 ms | 4728 KB | Output is correct |
4 | Correct | 54 ms | 1656 KB | Output is correct |
5 | Correct | 234 ms | 5112 KB | Output is correct |
6 | Correct | 233 ms | 4984 KB | Output is correct |
7 | Correct | 93 ms | 2936 KB | Output is correct |
8 | Correct | 107 ms | 3064 KB | Output is correct |
9 | Correct | 214 ms | 4604 KB | Output is correct |
10 | Correct | 220 ms | 4600 KB | Output is correct |
11 | Correct | 193 ms | 4216 KB | Output is correct |
12 | Correct | 189 ms | 4344 KB | Output is correct |
13 | Correct | 175 ms | 4216 KB | Output is correct |
14 | Correct | 167 ms | 3832 KB | Output is correct |
15 | Correct | 166 ms | 3960 KB | Output is correct |
16 | Correct | 165 ms | 3704 KB | Output is correct |
17 | Correct | 227 ms | 4856 KB | Output is correct |
18 | Correct | 214 ms | 4856 KB | Output is correct |
19 | Correct | 236 ms | 4856 KB | Output is correct |
20 | Correct | 223 ms | 4728 KB | Output is correct |
21 | Correct | 214 ms | 4856 KB | Output is correct |
22 | Correct | 231 ms | 4728 KB | Output is correct |
23 | Correct | 223 ms | 4856 KB | Output is correct |
24 | Correct | 228 ms | 4856 KB | Output is correct |
25 | Correct | 228 ms | 4728 KB | Output is correct |
26 | Correct | 223 ms | 4728 KB | Output is correct |
27 | Correct | 220 ms | 4856 KB | Output is correct |
28 | Correct | 224 ms | 4728 KB | Output is correct |
29 | Correct | 224 ms | 4728 KB | Output is correct |
30 | Correct | 231 ms | 4984 KB | Output is correct |
31 | Correct | 234 ms | 4856 KB | Output is correct |
32 | Correct | 229 ms | 4984 KB | Output is correct |
33 | Correct | 5 ms | 760 KB | Output is correct |
34 | Correct | 6 ms | 760 KB | Output is correct |
35 | Correct | 5 ms | 760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 202 ms | 4348 KB | Output is correct |
2 | Correct | 225 ms | 5112 KB | Output is correct |
3 | Correct | 227 ms | 4728 KB | Output is correct |
4 | Correct | 54 ms | 1656 KB | Output is correct |
5 | Correct | 234 ms | 5112 KB | Output is correct |
6 | Correct | 233 ms | 4984 KB | Output is correct |
7 | Correct | 93 ms | 2936 KB | Output is correct |
8 | Correct | 107 ms | 3064 KB | Output is correct |
9 | Correct | 214 ms | 4604 KB | Output is correct |
10 | Correct | 220 ms | 4600 KB | Output is correct |
11 | Correct | 193 ms | 4216 KB | Output is correct |
12 | Correct | 189 ms | 4344 KB | Output is correct |
13 | Correct | 175 ms | 4216 KB | Output is correct |
14 | Correct | 167 ms | 3832 KB | Output is correct |
15 | Correct | 166 ms | 3960 KB | Output is correct |
16 | Correct | 165 ms | 3704 KB | Output is correct |
17 | Correct | 227 ms | 4856 KB | Output is correct |
18 | Correct | 214 ms | 4856 KB | Output is correct |
19 | Correct | 236 ms | 4856 KB | Output is correct |
20 | Correct | 223 ms | 4728 KB | Output is correct |
21 | Correct | 214 ms | 4856 KB | Output is correct |
22 | Correct | 231 ms | 4728 KB | Output is correct |
23 | Correct | 223 ms | 4856 KB | Output is correct |
24 | Correct | 228 ms | 4856 KB | Output is correct |
25 | Correct | 228 ms | 4728 KB | Output is correct |
26 | Correct | 223 ms | 4728 KB | Output is correct |
27 | Correct | 220 ms | 4856 KB | Output is correct |
28 | Correct | 224 ms | 4728 KB | Output is correct |
29 | Correct | 224 ms | 4728 KB | Output is correct |
30 | Correct | 231 ms | 4984 KB | Output is correct |
31 | Correct | 234 ms | 4856 KB | Output is correct |
32 | Correct | 229 ms | 4984 KB | Output is correct |
33 | Correct | 5 ms | 760 KB | Output is correct |
34 | Correct | 6 ms | 760 KB | Output is correct |
35 | Correct | 5 ms | 760 KB | Output is correct |
36 | Correct | 1056 ms | 19576 KB | Output is correct |
37 | Correct | 1185 ms | 23416 KB | Output is correct |
38 | Correct | 1199 ms | 23800 KB | Output is correct |
39 | Correct | 428 ms | 9720 KB | Output is correct |
40 | Correct | 1199 ms | 23696 KB | Output is correct |
41 | Correct | 625 ms | 13944 KB | Output is correct |
42 | Correct | 607 ms | 14076 KB | Output is correct |
43 | Correct | 827 ms | 18040 KB | Output is correct |
44 | Correct | 1177 ms | 24356 KB | Output is correct |
45 | Correct | 1191 ms | 23800 KB | Output is correct |
46 | Correct | 1201 ms | 23800 KB | Output is correct |
47 | Correct | 1051 ms | 22012 KB | Output is correct |
48 | Correct | 1047 ms | 21140 KB | Output is correct |
49 | Correct | 905 ms | 18592 KB | Output is correct |
50 | Correct | 900 ms | 18424 KB | Output is correct |
51 | Correct | 1012 ms | 19960 KB | Output is correct |
52 | Correct | 1173 ms | 22776 KB | Output is correct |
53 | Correct | 1167 ms | 22648 KB | Output is correct |
54 | Correct | 1128 ms | 21752 KB | Output is correct |
55 | Correct | 1151 ms | 21880 KB | Output is correct |
56 | Correct | 1122 ms | 21880 KB | Output is correct |
57 | Correct | 1179 ms | 22976 KB | Output is correct |
58 | Correct | 1167 ms | 22904 KB | Output is correct |
59 | Correct | 1134 ms | 22776 KB | Output is correct |
60 | Correct | 1166 ms | 22776 KB | Output is correct |
61 | Correct | 1162 ms | 22776 KB | Output is correct |
62 | Correct | 1175 ms | 23048 KB | Output is correct |
63 | Correct | 1134 ms | 22908 KB | Output is correct |
64 | Correct | 1158 ms | 22752 KB | Output is correct |
65 | Correct | 1190 ms | 22776 KB | Output is correct |
66 | Correct | 1156 ms | 22776 KB | Output is correct |
67 | Correct | 1158 ms | 22776 KB | Output is correct |
68 | Correct | 1155 ms | 22776 KB | Output is correct |
69 | Correct | 1153 ms | 22648 KB | Output is correct |
70 | Correct | 1184 ms | 22776 KB | Output is correct |
71 | Correct | 1161 ms | 22776 KB | Output is correct |
72 | Correct | 1182 ms | 22904 KB | Output is correct |
73 | Correct | 1187 ms | 22752 KB | Output is correct |
74 | Correct | 5 ms | 632 KB | Output is correct |
75 | Correct | 6 ms | 760 KB | Output is correct |
76 | Correct | 5 ms | 760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 760 KB | Output is correct |
2 | Correct | 6 ms | 764 KB | Output is correct |
3 | Correct | 6 ms | 760 KB | Output is correct |
4 | Correct | 5 ms | 760 KB | Output is correct |
5 | Correct | 5 ms | 760 KB | Output is correct |
6 | Correct | 6 ms | 760 KB | Output is correct |
7 | Correct | 5 ms | 760 KB | Output is correct |
8 | Correct | 5 ms | 760 KB | Output is correct |
9 | Correct | 5 ms | 760 KB | Output is correct |
10 | Correct | 5 ms | 760 KB | Output is correct |
11 | Correct | 6 ms | 888 KB | Output is correct |
12 | Correct | 6 ms | 760 KB | Output is correct |
13 | Correct | 6 ms | 760 KB | Output is correct |
14 | Correct | 6 ms | 760 KB | Output is correct |
15 | Correct | 6 ms | 760 KB | Output is correct |
16 | Correct | 5 ms | 760 KB | Output is correct |
17 | Correct | 5 ms | 760 KB | Output is correct |
18 | Correct | 202 ms | 4348 KB | Output is correct |
19 | Correct | 225 ms | 5112 KB | Output is correct |
20 | Correct | 227 ms | 4728 KB | Output is correct |
21 | Correct | 54 ms | 1656 KB | Output is correct |
22 | Correct | 234 ms | 5112 KB | Output is correct |
23 | Correct | 233 ms | 4984 KB | Output is correct |
24 | Correct | 93 ms | 2936 KB | Output is correct |
25 | Correct | 107 ms | 3064 KB | Output is correct |
26 | Correct | 214 ms | 4604 KB | Output is correct |
27 | Correct | 220 ms | 4600 KB | Output is correct |
28 | Correct | 193 ms | 4216 KB | Output is correct |
29 | Correct | 189 ms | 4344 KB | Output is correct |
30 | Correct | 175 ms | 4216 KB | Output is correct |
31 | Correct | 167 ms | 3832 KB | Output is correct |
32 | Correct | 166 ms | 3960 KB | Output is correct |
33 | Correct | 165 ms | 3704 KB | Output is correct |
34 | Correct | 227 ms | 4856 KB | Output is correct |
35 | Correct | 214 ms | 4856 KB | Output is correct |
36 | Correct | 236 ms | 4856 KB | Output is correct |
37 | Correct | 223 ms | 4728 KB | Output is correct |
38 | Correct | 214 ms | 4856 KB | Output is correct |
39 | Correct | 231 ms | 4728 KB | Output is correct |
40 | Correct | 223 ms | 4856 KB | Output is correct |
41 | Correct | 228 ms | 4856 KB | Output is correct |
42 | Correct | 228 ms | 4728 KB | Output is correct |
43 | Correct | 223 ms | 4728 KB | Output is correct |
44 | Correct | 220 ms | 4856 KB | Output is correct |
45 | Correct | 224 ms | 4728 KB | Output is correct |
46 | Correct | 224 ms | 4728 KB | Output is correct |
47 | Correct | 231 ms | 4984 KB | Output is correct |
48 | Correct | 234 ms | 4856 KB | Output is correct |
49 | Correct | 229 ms | 4984 KB | Output is correct |
50 | Correct | 5 ms | 760 KB | Output is correct |
51 | Correct | 6 ms | 760 KB | Output is correct |
52 | Correct | 5 ms | 760 KB | Output is correct |
53 | Correct | 1056 ms | 19576 KB | Output is correct |
54 | Correct | 1185 ms | 23416 KB | Output is correct |
55 | Correct | 1199 ms | 23800 KB | Output is correct |
56 | Correct | 428 ms | 9720 KB | Output is correct |
57 | Correct | 1199 ms | 23696 KB | Output is correct |
58 | Correct | 625 ms | 13944 KB | Output is correct |
59 | Correct | 607 ms | 14076 KB | Output is correct |
60 | Correct | 827 ms | 18040 KB | Output is correct |
61 | Correct | 1177 ms | 24356 KB | Output is correct |
62 | Correct | 1191 ms | 23800 KB | Output is correct |
63 | Correct | 1201 ms | 23800 KB | Output is correct |
64 | Correct | 1051 ms | 22012 KB | Output is correct |
65 | Correct | 1047 ms | 21140 KB | Output is correct |
66 | Correct | 905 ms | 18592 KB | Output is correct |
67 | Correct | 900 ms | 18424 KB | Output is correct |
68 | Correct | 1012 ms | 19960 KB | Output is correct |
69 | Correct | 1173 ms | 22776 KB | Output is correct |
70 | Correct | 1167 ms | 22648 KB | Output is correct |
71 | Correct | 1128 ms | 21752 KB | Output is correct |
72 | Correct | 1151 ms | 21880 KB | Output is correct |
73 | Correct | 1122 ms | 21880 KB | Output is correct |
74 | Correct | 1179 ms | 22976 KB | Output is correct |
75 | Correct | 1167 ms | 22904 KB | Output is correct |
76 | Correct | 1134 ms | 22776 KB | Output is correct |
77 | Correct | 1166 ms | 22776 KB | Output is correct |
78 | Correct | 1162 ms | 22776 KB | Output is correct |
79 | Correct | 1175 ms | 23048 KB | Output is correct |
80 | Correct | 1134 ms | 22908 KB | Output is correct |
81 | Correct | 1158 ms | 22752 KB | Output is correct |
82 | Correct | 1190 ms | 22776 KB | Output is correct |
83 | Correct | 1156 ms | 22776 KB | Output is correct |
84 | Correct | 1158 ms | 22776 KB | Output is correct |
85 | Correct | 1155 ms | 22776 KB | Output is correct |
86 | Correct | 1153 ms | 22648 KB | Output is correct |
87 | Correct | 1184 ms | 22776 KB | Output is correct |
88 | Correct | 1161 ms | 22776 KB | Output is correct |
89 | Correct | 1182 ms | 22904 KB | Output is correct |
90 | Correct | 1187 ms | 22752 KB | Output is correct |
91 | Correct | 5 ms | 632 KB | Output is correct |
92 | Correct | 6 ms | 760 KB | Output is correct |
93 | Correct | 5 ms | 760 KB | Output is correct |
94 | Correct | 1176 ms | 22136 KB | Output is correct |
95 | Correct | 1214 ms | 21912 KB | Output is correct |
96 | Correct | 1245 ms | 22136 KB | Output is correct |
97 | Correct | 695 ms | 13176 KB | Output is correct |
98 | Correct | 429 ms | 8440 KB | Output is correct |
99 | Correct | 1198 ms | 22008 KB | Output is correct |
100 | Correct | 609 ms | 12664 KB | Output is correct |
101 | Correct | 617 ms | 12548 KB | Output is correct |
102 | Correct | 902 ms | 16120 KB | Output is correct |
103 | Correct | 1204 ms | 22392 KB | Output is correct |
104 | Correct | 1242 ms | 22396 KB | Output is correct |
105 | Correct | 1255 ms | 22392 KB | Output is correct |
106 | Correct | 1163 ms | 21752 KB | Output is correct |
107 | Correct | 1034 ms | 20344 KB | Output is correct |
108 | Correct | 912 ms | 17784 KB | Output is correct |
109 | Correct | 1058 ms | 20088 KB | Output is correct |
110 | Correct | 1008 ms | 18552 KB | Output is correct |
111 | Correct | 1203 ms | 22648 KB | Output is correct |
112 | Correct | 1256 ms | 22392 KB | Output is correct |
113 | Correct | 1153 ms | 21112 KB | Output is correct |
114 | Correct | 1121 ms | 21112 KB | Output is correct |
115 | Correct | 1186 ms | 21112 KB | Output is correct |
116 | Correct | 1215 ms | 22392 KB | Output is correct |
117 | Correct | 1232 ms | 22392 KB | Output is correct |
118 | Correct | 1223 ms | 22392 KB | Output is correct |
119 | Correct | 1217 ms | 22392 KB | Output is correct |
120 | Correct | 1220 ms | 22392 KB | Output is correct |
121 | Correct | 1046 ms | 20320 KB | Output is correct |
122 | Correct | 1184 ms | 22136 KB | Output is correct |
123 | Correct | 1219 ms | 22264 KB | Output is correct |
124 | Correct | 5 ms | 760 KB | Output is correct |
125 | Correct | 6 ms | 760 KB | Output is correct |
126 | Correct | 5 ms | 764 KB | Output is correct |