/*input
4 3 1
ACC
CCA
ACA
AAA
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//order_of_key #of elements less than x
// find_by_order kth element
typedef unsigned long long int ll;
#define ld long double
#define pii pair<int,int>
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=5e3+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=998244353;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
out<<P.f+1<<' '<<P.s+1;
return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?"\n":"");
return out;
}
int mult(ll a,ll b){
if(a<0) a+=MOD;
return (a*b)%MOD;
}
ll mypow(ll a,ll b){
if(b<=0) return 1;
ll res=1LL;
while(b){
if(b&1) res=mult(res,a);
a=mult(a,a);
b>>=1;
}
return res;
}
int arr[maxn][maxn];
bool vis[maxn];
int k;
mt19937_64 rng(69);
bool ok[maxn];
ll val[maxn];
ll tot[4][maxn];
int32_t main(){
ios::sync_with_stdio(false),cin.tie(0);
int n,m;
cin>>n>>m>>k;
REP(i,n){
REP(j,m){
char c;
cin>>c;
int v=0;
if(c=='C') v=1;
if(c=='G') v=2;
if(c=='T') v=3;
arr[i][j]=v;
}
ok[i]=1;
}
int cnt=n;
while(cnt>1){
REP(i,n) val[i]=rng();
REP(a,4) REP(i,m) tot[a][i]=0;
ll ts=0;
REP(i,n){
ts+=val[i];
REP(j,m){
tot[arr[i][j]][j]+=val[i];
}
}
REP(i,n){
if(!ok[i]) continue;
ll tmp=ts*m;
REP(j,m) tmp-=tot[arr[i][j]][j];
if((ts-val[i])*k!=tmp) ok[i]=0,--cnt;
}
}
REP(i,n){
if(ok[i]){
cout<<i+1;
return 0;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
600 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
848 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
724 KB |
Output is correct |
14 |
Correct |
1 ms |
736 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
16 |
Correct |
1 ms |
728 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
16908 KB |
Output is correct |
2 |
Correct |
86 ms |
23416 KB |
Output is correct |
3 |
Correct |
84 ms |
22436 KB |
Output is correct |
4 |
Correct |
20 ms |
8216 KB |
Output is correct |
5 |
Correct |
90 ms |
23384 KB |
Output is correct |
6 |
Correct |
84 ms |
23496 KB |
Output is correct |
7 |
Correct |
38 ms |
10144 KB |
Output is correct |
8 |
Correct |
37 ms |
10208 KB |
Output is correct |
9 |
Correct |
78 ms |
21844 KB |
Output is correct |
10 |
Correct |
85 ms |
21920 KB |
Output is correct |
11 |
Correct |
70 ms |
19204 KB |
Output is correct |
12 |
Correct |
69 ms |
19372 KB |
Output is correct |
13 |
Correct |
68 ms |
19228 KB |
Output is correct |
14 |
Correct |
60 ms |
16552 KB |
Output is correct |
15 |
Correct |
65 ms |
16748 KB |
Output is correct |
16 |
Correct |
61 ms |
17300 KB |
Output is correct |
17 |
Correct |
86 ms |
22488 KB |
Output is correct |
18 |
Correct |
85 ms |
22252 KB |
Output is correct |
19 |
Correct |
82 ms |
22484 KB |
Output is correct |
20 |
Correct |
85 ms |
22112 KB |
Output is correct |
21 |
Correct |
83 ms |
22360 KB |
Output is correct |
22 |
Correct |
81 ms |
22264 KB |
Output is correct |
23 |
Correct |
82 ms |
22388 KB |
Output is correct |
24 |
Correct |
88 ms |
22336 KB |
Output is correct |
25 |
Correct |
80 ms |
22124 KB |
Output is correct |
26 |
Correct |
85 ms |
22348 KB |
Output is correct |
27 |
Correct |
79 ms |
22228 KB |
Output is correct |
28 |
Correct |
81 ms |
22184 KB |
Output is correct |
29 |
Correct |
87 ms |
22324 KB |
Output is correct |
30 |
Correct |
98 ms |
23488 KB |
Output is correct |
31 |
Correct |
86 ms |
23436 KB |
Output is correct |
32 |
Correct |
87 ms |
23460 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
1 ms |
724 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
16908 KB |
Output is correct |
2 |
Correct |
86 ms |
23416 KB |
Output is correct |
3 |
Correct |
84 ms |
22436 KB |
Output is correct |
4 |
Correct |
20 ms |
8216 KB |
Output is correct |
5 |
Correct |
90 ms |
23384 KB |
Output is correct |
6 |
Correct |
84 ms |
23496 KB |
Output is correct |
7 |
Correct |
38 ms |
10144 KB |
Output is correct |
8 |
Correct |
37 ms |
10208 KB |
Output is correct |
9 |
Correct |
78 ms |
21844 KB |
Output is correct |
10 |
Correct |
85 ms |
21920 KB |
Output is correct |
11 |
Correct |
70 ms |
19204 KB |
Output is correct |
12 |
Correct |
69 ms |
19372 KB |
Output is correct |
13 |
Correct |
68 ms |
19228 KB |
Output is correct |
14 |
Correct |
60 ms |
16552 KB |
Output is correct |
15 |
Correct |
65 ms |
16748 KB |
Output is correct |
16 |
Correct |
61 ms |
17300 KB |
Output is correct |
17 |
Correct |
86 ms |
22488 KB |
Output is correct |
18 |
Correct |
85 ms |
22252 KB |
Output is correct |
19 |
Correct |
82 ms |
22484 KB |
Output is correct |
20 |
Correct |
85 ms |
22112 KB |
Output is correct |
21 |
Correct |
83 ms |
22360 KB |
Output is correct |
22 |
Correct |
81 ms |
22264 KB |
Output is correct |
23 |
Correct |
82 ms |
22388 KB |
Output is correct |
24 |
Correct |
88 ms |
22336 KB |
Output is correct |
25 |
Correct |
80 ms |
22124 KB |
Output is correct |
26 |
Correct |
85 ms |
22348 KB |
Output is correct |
27 |
Correct |
79 ms |
22228 KB |
Output is correct |
28 |
Correct |
81 ms |
22184 KB |
Output is correct |
29 |
Correct |
87 ms |
22324 KB |
Output is correct |
30 |
Correct |
98 ms |
23488 KB |
Output is correct |
31 |
Correct |
86 ms |
23436 KB |
Output is correct |
32 |
Correct |
87 ms |
23460 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
1 ms |
724 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
36 |
Correct |
392 ms |
85108 KB |
Output is correct |
37 |
Correct |
431 ms |
97236 KB |
Output is correct |
38 |
Correct |
414 ms |
95104 KB |
Output is correct |
39 |
Correct |
173 ms |
43512 KB |
Output is correct |
40 |
Correct |
431 ms |
97008 KB |
Output is correct |
41 |
Correct |
217 ms |
48772 KB |
Output is correct |
42 |
Correct |
227 ms |
48740 KB |
Output is correct |
43 |
Correct |
303 ms |
72648 KB |
Output is correct |
44 |
Correct |
433 ms |
97120 KB |
Output is correct |
45 |
Correct |
432 ms |
97160 KB |
Output is correct |
46 |
Correct |
436 ms |
97116 KB |
Output is correct |
47 |
Correct |
375 ms |
85140 KB |
Output is correct |
48 |
Correct |
397 ms |
85064 KB |
Output is correct |
49 |
Correct |
331 ms |
72976 KB |
Output is correct |
50 |
Correct |
331 ms |
72932 KB |
Output is correct |
51 |
Correct |
362 ms |
82044 KB |
Output is correct |
52 |
Correct |
433 ms |
94784 KB |
Output is correct |
53 |
Correct |
414 ms |
94684 KB |
Output is correct |
54 |
Correct |
432 ms |
94600 KB |
Output is correct |
55 |
Correct |
411 ms |
94580 KB |
Output is correct |
56 |
Correct |
410 ms |
94608 KB |
Output is correct |
57 |
Correct |
451 ms |
95028 KB |
Output is correct |
58 |
Correct |
430 ms |
95044 KB |
Output is correct |
59 |
Correct |
427 ms |
94500 KB |
Output is correct |
60 |
Correct |
428 ms |
95116 KB |
Output is correct |
61 |
Correct |
428 ms |
94476 KB |
Output is correct |
62 |
Correct |
425 ms |
94120 KB |
Output is correct |
63 |
Correct |
422 ms |
94980 KB |
Output is correct |
64 |
Correct |
464 ms |
94856 KB |
Output is correct |
65 |
Correct |
431 ms |
94612 KB |
Output is correct |
66 |
Correct |
415 ms |
94824 KB |
Output is correct |
67 |
Correct |
431 ms |
95176 KB |
Output is correct |
68 |
Correct |
427 ms |
94992 KB |
Output is correct |
69 |
Correct |
451 ms |
94552 KB |
Output is correct |
70 |
Correct |
415 ms |
94984 KB |
Output is correct |
71 |
Correct |
444 ms |
94420 KB |
Output is correct |
72 |
Correct |
427 ms |
95272 KB |
Output is correct |
73 |
Correct |
431 ms |
94624 KB |
Output is correct |
74 |
Correct |
0 ms |
340 KB |
Output is correct |
75 |
Correct |
1 ms |
724 KB |
Output is correct |
76 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
600 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
848 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
724 KB |
Output is correct |
14 |
Correct |
1 ms |
736 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
16 |
Correct |
1 ms |
728 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
67 ms |
16908 KB |
Output is correct |
19 |
Correct |
86 ms |
23416 KB |
Output is correct |
20 |
Correct |
84 ms |
22436 KB |
Output is correct |
21 |
Correct |
20 ms |
8216 KB |
Output is correct |
22 |
Correct |
90 ms |
23384 KB |
Output is correct |
23 |
Correct |
84 ms |
23496 KB |
Output is correct |
24 |
Correct |
38 ms |
10144 KB |
Output is correct |
25 |
Correct |
37 ms |
10208 KB |
Output is correct |
26 |
Correct |
78 ms |
21844 KB |
Output is correct |
27 |
Correct |
85 ms |
21920 KB |
Output is correct |
28 |
Correct |
70 ms |
19204 KB |
Output is correct |
29 |
Correct |
69 ms |
19372 KB |
Output is correct |
30 |
Correct |
68 ms |
19228 KB |
Output is correct |
31 |
Correct |
60 ms |
16552 KB |
Output is correct |
32 |
Correct |
65 ms |
16748 KB |
Output is correct |
33 |
Correct |
61 ms |
17300 KB |
Output is correct |
34 |
Correct |
86 ms |
22488 KB |
Output is correct |
35 |
Correct |
85 ms |
22252 KB |
Output is correct |
36 |
Correct |
82 ms |
22484 KB |
Output is correct |
37 |
Correct |
85 ms |
22112 KB |
Output is correct |
38 |
Correct |
83 ms |
22360 KB |
Output is correct |
39 |
Correct |
81 ms |
22264 KB |
Output is correct |
40 |
Correct |
82 ms |
22388 KB |
Output is correct |
41 |
Correct |
88 ms |
22336 KB |
Output is correct |
42 |
Correct |
80 ms |
22124 KB |
Output is correct |
43 |
Correct |
85 ms |
22348 KB |
Output is correct |
44 |
Correct |
79 ms |
22228 KB |
Output is correct |
45 |
Correct |
81 ms |
22184 KB |
Output is correct |
46 |
Correct |
87 ms |
22324 KB |
Output is correct |
47 |
Correct |
98 ms |
23488 KB |
Output is correct |
48 |
Correct |
86 ms |
23436 KB |
Output is correct |
49 |
Correct |
87 ms |
23460 KB |
Output is correct |
50 |
Correct |
1 ms |
344 KB |
Output is correct |
51 |
Correct |
1 ms |
724 KB |
Output is correct |
52 |
Correct |
1 ms |
344 KB |
Output is correct |
53 |
Correct |
392 ms |
85108 KB |
Output is correct |
54 |
Correct |
431 ms |
97236 KB |
Output is correct |
55 |
Correct |
414 ms |
95104 KB |
Output is correct |
56 |
Correct |
173 ms |
43512 KB |
Output is correct |
57 |
Correct |
431 ms |
97008 KB |
Output is correct |
58 |
Correct |
217 ms |
48772 KB |
Output is correct |
59 |
Correct |
227 ms |
48740 KB |
Output is correct |
60 |
Correct |
303 ms |
72648 KB |
Output is correct |
61 |
Correct |
433 ms |
97120 KB |
Output is correct |
62 |
Correct |
432 ms |
97160 KB |
Output is correct |
63 |
Correct |
436 ms |
97116 KB |
Output is correct |
64 |
Correct |
375 ms |
85140 KB |
Output is correct |
65 |
Correct |
397 ms |
85064 KB |
Output is correct |
66 |
Correct |
331 ms |
72976 KB |
Output is correct |
67 |
Correct |
331 ms |
72932 KB |
Output is correct |
68 |
Correct |
362 ms |
82044 KB |
Output is correct |
69 |
Correct |
433 ms |
94784 KB |
Output is correct |
70 |
Correct |
414 ms |
94684 KB |
Output is correct |
71 |
Correct |
432 ms |
94600 KB |
Output is correct |
72 |
Correct |
411 ms |
94580 KB |
Output is correct |
73 |
Correct |
410 ms |
94608 KB |
Output is correct |
74 |
Correct |
451 ms |
95028 KB |
Output is correct |
75 |
Correct |
430 ms |
95044 KB |
Output is correct |
76 |
Correct |
427 ms |
94500 KB |
Output is correct |
77 |
Correct |
428 ms |
95116 KB |
Output is correct |
78 |
Correct |
428 ms |
94476 KB |
Output is correct |
79 |
Correct |
425 ms |
94120 KB |
Output is correct |
80 |
Correct |
422 ms |
94980 KB |
Output is correct |
81 |
Correct |
464 ms |
94856 KB |
Output is correct |
82 |
Correct |
431 ms |
94612 KB |
Output is correct |
83 |
Correct |
415 ms |
94824 KB |
Output is correct |
84 |
Correct |
431 ms |
95176 KB |
Output is correct |
85 |
Correct |
427 ms |
94992 KB |
Output is correct |
86 |
Correct |
451 ms |
94552 KB |
Output is correct |
87 |
Correct |
415 ms |
94984 KB |
Output is correct |
88 |
Correct |
444 ms |
94420 KB |
Output is correct |
89 |
Correct |
427 ms |
95272 KB |
Output is correct |
90 |
Correct |
431 ms |
94624 KB |
Output is correct |
91 |
Correct |
0 ms |
340 KB |
Output is correct |
92 |
Correct |
1 ms |
724 KB |
Output is correct |
93 |
Correct |
0 ms |
340 KB |
Output is correct |
94 |
Correct |
432 ms |
91964 KB |
Output is correct |
95 |
Correct |
445 ms |
97340 KB |
Output is correct |
96 |
Correct |
458 ms |
95380 KB |
Output is correct |
97 |
Correct |
239 ms |
52124 KB |
Output is correct |
98 |
Correct |
177 ms |
43432 KB |
Output is correct |
99 |
Correct |
441 ms |
97008 KB |
Output is correct |
100 |
Correct |
246 ms |
48780 KB |
Output is correct |
101 |
Correct |
220 ms |
48692 KB |
Output is correct |
102 |
Correct |
330 ms |
72768 KB |
Output is correct |
103 |
Correct |
447 ms |
97084 KB |
Output is correct |
104 |
Correct |
443 ms |
97104 KB |
Output is correct |
105 |
Correct |
491 ms |
97180 KB |
Output is correct |
106 |
Correct |
427 ms |
92228 KB |
Output is correct |
107 |
Correct |
387 ms |
85112 KB |
Output is correct |
108 |
Correct |
330 ms |
72988 KB |
Output is correct |
109 |
Correct |
404 ms |
83812 KB |
Output is correct |
110 |
Correct |
397 ms |
81664 KB |
Output is correct |
111 |
Correct |
473 ms |
97252 KB |
Output is correct |
112 |
Correct |
449 ms |
95892 KB |
Output is correct |
113 |
Correct |
427 ms |
94488 KB |
Output is correct |
114 |
Correct |
431 ms |
94488 KB |
Output is correct |
115 |
Correct |
422 ms |
94484 KB |
Output is correct |
116 |
Correct |
446 ms |
95760 KB |
Output is correct |
117 |
Correct |
439 ms |
96008 KB |
Output is correct |
118 |
Correct |
451 ms |
96048 KB |
Output is correct |
119 |
Correct |
460 ms |
95608 KB |
Output is correct |
120 |
Correct |
442 ms |
95964 KB |
Output is correct |
121 |
Correct |
416 ms |
85068 KB |
Output is correct |
122 |
Correct |
438 ms |
97288 KB |
Output is correct |
123 |
Correct |
437 ms |
94884 KB |
Output is correct |
124 |
Correct |
1 ms |
340 KB |
Output is correct |
125 |
Correct |
1 ms |
724 KB |
Output is correct |
126 |
Correct |
1 ms |
340 KB |
Output is correct |