oj.uz

답안 #441797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
441797 2021-07-06T07:55:41 Z Haruto810198 Genetics (BOI18_genetics) C++17
100 / 100
 546 ms 174856 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int,int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 4110;

int n, m, k;
string str[MAX];
vi arr[MAX];
int w[MAX];
int csum[MAX][4];
int req;
int res;

void check(int id){

    int sum = 0;
    req -= w[id] * k;

    FOR(j, 0, m-1, 1){
        FOR(c, 0, 3, 1){
            if(c == arr[id][j]) continue;
            sum += csum[j][c];
        }
    }

    if(sum==req){
        res = id;
    }

    //cerr<<sum<<" "<<req<<endl;
    req += w[id] * k;

}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    srand(time(NULL));

    cin>>n>>m>>k;
    FOR(i, 1, n, 1){
        cin>>str[i];
    }

    FOR(i, 1, n, 1){
        FOR(j, 0, m-1, 1){
            if(str[i][j]=='A'){
                arr[i].pb(0);
            }
            else if(str[i][j]=='C'){
                arr[i].pb(1);
            }
            else if(str[i][j]=='G'){
                arr[i].pb(2);
            }
            else if(str[i][j]=='T'){
                arr[i].pb(3);
            }
        }
    }

    FOR(i, 1, n, 1){
        w[i] = rand();
        req += w[i];
    }
    req *= k;

    FOR(i, 1, n, 1){
        FOR(j, 0, m-1, 1){
            csum[j][arr[i][j]] += w[i];
        }
    }

    FOR(i, 1, n, 1){
        check(i);
    }

    cout<<res<<'\n';

    return 0;

}

Subtask #1
27.0 / 27.0

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

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 30164 KB Output is correct
2 Correct 83 ms 36004 KB Output is correct
3 Correct 84 ms 34464 KB Output is correct
4 Correct 23 ms 11040 KB Output is correct
5 Correct 90 ms 35992 KB Output is correct
6 Correct 88 ms 36000 KB Output is correct
7 Correct 37 ms 15688 KB Output is correct
8 Correct 35 ms 15684 KB Output is correct
9 Correct 83 ms 34400 KB Output is correct
10 Correct 84 ms 34348 KB Output is correct
11 Correct 74 ms 30072 KB Output is correct
12 Correct 72 ms 30316 KB Output is correct
13 Correct 86 ms 30196 KB Output is correct
14 Correct 62 ms 25988 KB Output is correct
15 Correct 66 ms 26280 KB Output is correct
16 Correct 67 ms 28780 KB Output is correct
17 Correct 84 ms 34552 KB Output is correct
18 Correct 84 ms 34236 KB Output is correct
19 Correct 85 ms 34504 KB Output is correct
20 Correct 87 ms 34120 KB Output is correct
21 Correct 97 ms 34372 KB Output is correct
22 Correct 85 ms 34116 KB Output is correct
23 Correct 84 ms 34392 KB Output is correct
24 Correct 83 ms 34276 KB Output is correct
25 Correct 84 ms 34120 KB Output is correct
26 Correct 84 ms 34420 KB Output is correct
27 Correct 86 ms 34204 KB Output is correct
28 Correct 86 ms 34128 KB Output is correct
29 Correct 89 ms 34372 KB Output is correct
30 Correct 79 ms 35940 KB Output is correct
31 Correct 80 ms 35976 KB Output is correct
32 Correct 90 ms 35904 KB Output is correct
33 Correct 1 ms 460 KB Output is correct
34 Correct 1 ms 636 KB Output is correct
35 Correct 1 ms 460 KB Output is correct

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 30164 KB Output is correct
2 Correct 83 ms 36004 KB Output is correct
3 Correct 84 ms 34464 KB Output is correct
4 Correct 23 ms 11040 KB Output is correct
5 Correct 90 ms 35992 KB Output is correct
6 Correct 88 ms 36000 KB Output is correct
7 Correct 37 ms 15688 KB Output is correct
8 Correct 35 ms 15684 KB Output is correct
9 Correct 83 ms 34400 KB Output is correct
10 Correct 84 ms 34348 KB Output is correct
11 Correct 74 ms 30072 KB Output is correct
12 Correct 72 ms 30316 KB Output is correct
13 Correct 86 ms 30196 KB Output is correct
14 Correct 62 ms 25988 KB Output is correct
15 Correct 66 ms 26280 KB Output is correct
16 Correct 67 ms 28780 KB Output is correct
17 Correct 84 ms 34552 KB Output is correct
18 Correct 84 ms 34236 KB Output is correct
19 Correct 85 ms 34504 KB Output is correct
20 Correct 87 ms 34120 KB Output is correct
21 Correct 97 ms 34372 KB Output is correct
22 Correct 85 ms 34116 KB Output is correct
23 Correct 84 ms 34392 KB Output is correct
24 Correct 83 ms 34276 KB Output is correct
25 Correct 84 ms 34120 KB Output is correct
26 Correct 84 ms 34420 KB Output is correct
27 Correct 86 ms 34204 KB Output is correct
28 Correct 86 ms 34128 KB Output is correct
29 Correct 89 ms 34372 KB Output is correct
30 Correct 79 ms 35940 KB Output is correct
31 Correct 80 ms 35976 KB Output is correct
32 Correct 90 ms 35904 KB Output is correct
33 Correct 1 ms 460 KB Output is correct
34 Correct 1 ms 636 KB Output is correct
35 Correct 1 ms 460 KB Output is correct
36 Correct 378 ms 138580 KB Output is correct
37 Correct 411 ms 174472 KB Output is correct
38 Correct 423 ms 155696 KB Output is correct
39 Correct 164 ms 68072 KB Output is correct
40 Correct 442 ms 174668 KB Output is correct
41 Correct 225 ms 91956 KB Output is correct
42 Correct 217 ms 91912 KB Output is correct
43 Correct 317 ms 128836 KB Output is correct
44 Correct 432 ms 158988 KB Output is correct
45 Correct 430 ms 158832 KB Output is correct
46 Correct 434 ms 158912 KB Output is correct
47 Correct 372 ms 140456 KB Output is correct
48 Correct 381 ms 140564 KB Output is correct
49 Correct 328 ms 121412 KB Output is correct
50 Correct 324 ms 121580 KB Output is correct
51 Correct 380 ms 149312 KB Output is correct
52 Correct 426 ms 155480 KB Output is correct
53 Correct 428 ms 155540 KB Output is correct
54 Correct 380 ms 154520 KB Output is correct
55 Correct 380 ms 154460 KB Output is correct
56 Correct 441 ms 154428 KB Output is correct
57 Correct 429 ms 156032 KB Output is correct
58 Correct 438 ms 155972 KB Output is correct
59 Correct 427 ms 155232 KB Output is correct
60 Correct 426 ms 156088 KB Output is correct
61 Correct 441 ms 155312 KB Output is correct
62 Correct 432 ms 154652 KB Output is correct
63 Correct 438 ms 156092 KB Output is correct
64 Correct 428 ms 155972 KB Output is correct
65 Correct 430 ms 155460 KB Output is correct
66 Correct 435 ms 155544 KB Output is correct
67 Correct 445 ms 156088 KB Output is correct
68 Correct 444 ms 156180 KB Output is correct
69 Correct 438 ms 155348 KB Output is correct
70 Correct 431 ms 155780 KB Output is correct
71 Correct 437 ms 155164 KB Output is correct
72 Correct 432 ms 156440 KB Output is correct
73 Correct 429 ms 155412 KB Output is correct
74 Correct 1 ms 460 KB Output is correct
75 Correct 1 ms 588 KB Output is correct
76 Correct 1 ms 460 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 588 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 75 ms 30164 KB Output is correct
19 Correct 83 ms 36004 KB Output is correct
20 Correct 84 ms 34464 KB Output is correct
21 Correct 23 ms 11040 KB Output is correct
22 Correct 90 ms 35992 KB Output is correct
23 Correct 88 ms 36000 KB Output is correct
24 Correct 37 ms 15688 KB Output is correct
25 Correct 35 ms 15684 KB Output is correct
26 Correct 83 ms 34400 KB Output is correct
27 Correct 84 ms 34348 KB Output is correct
28 Correct 74 ms 30072 KB Output is correct
29 Correct 72 ms 30316 KB Output is correct
30 Correct 86 ms 30196 KB Output is correct
31 Correct 62 ms 25988 KB Output is correct
32 Correct 66 ms 26280 KB Output is correct
33 Correct 67 ms 28780 KB Output is correct
34 Correct 84 ms 34552 KB Output is correct
35 Correct 84 ms 34236 KB Output is correct
36 Correct 85 ms 34504 KB Output is correct
37 Correct 87 ms 34120 KB Output is correct
38 Correct 97 ms 34372 KB Output is correct
39 Correct 85 ms 34116 KB Output is correct
40 Correct 84 ms 34392 KB Output is correct
41 Correct 83 ms 34276 KB Output is correct
42 Correct 84 ms 34120 KB Output is correct
43 Correct 84 ms 34420 KB Output is correct
44 Correct 86 ms 34204 KB Output is correct
45 Correct 86 ms 34128 KB Output is correct
46 Correct 89 ms 34372 KB Output is correct
47 Correct 79 ms 35940 KB Output is correct
48 Correct 80 ms 35976 KB Output is correct
49 Correct 90 ms 35904 KB Output is correct
50 Correct 1 ms 460 KB Output is correct
51 Correct 1 ms 636 KB Output is correct
52 Correct 1 ms 460 KB Output is correct
53 Correct 378 ms 138580 KB Output is correct
54 Correct 411 ms 174472 KB Output is correct
55 Correct 423 ms 155696 KB Output is correct
56 Correct 164 ms 68072 KB Output is correct
57 Correct 442 ms 174668 KB Output is correct
58 Correct 225 ms 91956 KB Output is correct
59 Correct 217 ms 91912 KB Output is correct
60 Correct 317 ms 128836 KB Output is correct
61 Correct 432 ms 158988 KB Output is correct
62 Correct 430 ms 158832 KB Output is correct
63 Correct 434 ms 158912 KB Output is correct
64 Correct 372 ms 140456 KB Output is correct
65 Correct 381 ms 140564 KB Output is correct
66 Correct 328 ms 121412 KB Output is correct
67 Correct 324 ms 121580 KB Output is correct
68 Correct 380 ms 149312 KB Output is correct
69 Correct 426 ms 155480 KB Output is correct
70 Correct 428 ms 155540 KB Output is correct
71 Correct 380 ms 154520 KB Output is correct
72 Correct 380 ms 154460 KB Output is correct
73 Correct 441 ms 154428 KB Output is correct
74 Correct 429 ms 156032 KB Output is correct
75 Correct 438 ms 155972 KB Output is correct
76 Correct 427 ms 155232 KB Output is correct
77 Correct 426 ms 156088 KB Output is correct
78 Correct 441 ms 155312 KB Output is correct
79 Correct 432 ms 154652 KB Output is correct
80 Correct 438 ms 156092 KB Output is correct
81 Correct 428 ms 155972 KB Output is correct
82 Correct 430 ms 155460 KB Output is correct
83 Correct 435 ms 155544 KB Output is correct
84 Correct 445 ms 156088 KB Output is correct
85 Correct 444 ms 156180 KB Output is correct
86 Correct 438 ms 155348 KB Output is correct
87 Correct 431 ms 155780 KB Output is correct
88 Correct 437 ms 155164 KB Output is correct
89 Correct 432 ms 156440 KB Output is correct
90 Correct 429 ms 155412 KB Output is correct
91 Correct 1 ms 460 KB Output is correct
92 Correct 1 ms 588 KB Output is correct
93 Correct 1 ms 460 KB Output is correct
94 Correct 491 ms 151328 KB Output is correct
95 Correct 491 ms 174788 KB Output is correct
96 Correct 521 ms 156744 KB Output is correct
97 Correct 307 ms 97752 KB Output is correct
98 Correct 183 ms 68064 KB Output is correct
99 Correct 466 ms 174776 KB Output is correct
100 Correct 274 ms 91972 KB Output is correct
101 Correct 288 ms 92212 KB Output is correct
102 Correct 406 ms 128908 KB Output is correct
103 Correct 469 ms 158904 KB Output is correct
104 Correct 546 ms 158916 KB Output is correct
105 Correct 526 ms 158916 KB Output is correct
106 Correct 507 ms 151816 KB Output is correct
107 Correct 407 ms 140692 KB Output is correct
108 Correct 340 ms 121708 KB Output is correct
109 Correct 480 ms 138892 KB Output is correct
110 Correct 461 ms 135084 KB Output is correct
111 Correct 521 ms 159080 KB Output is correct
112 Correct 529 ms 157636 KB Output is correct
113 Correct 416 ms 154944 KB Output is correct
114 Correct 388 ms 154980 KB Output is correct
115 Correct 508 ms 154820 KB Output is correct
116 Correct 538 ms 157508 KB Output is correct
117 Correct 525 ms 157964 KB Output is correct
118 Correct 513 ms 157636 KB Output is correct
119 Correct 512 ms 157332 KB Output is correct
120 Correct 511 ms 158000 KB Output is correct
121 Correct 384 ms 140884 KB Output is correct
122 Correct 411 ms 174856 KB Output is correct
123 Correct 423 ms 156116 KB Output is correct
124 Correct 1 ms 460 KB Output is correct
125 Correct 1 ms 588 KB Output is correct
126 Correct 1 ms 492 KB Output is correct