oj.uz

답안 #888351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
888351 2023-12-17T03:40:50 Z 1075508020060209tc Genetics (BOI18_genetics) C++14
27 / 100
 315 ms 392716 KB 
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
//const int mod=998244353;
unsigned long long seed=1234;
unsigned long long rnd(){
seed^=seed<<13;
seed^=seed>>7;
seed^=seed>>6;
return seed;
}

int n;int m;int K;
int gr[4105][4105];
int ps[4][4105][4105];
int mby[4105];
void init(){
cin>>n>>m>>K;
string s;
for(int i=1;i<=n;i++){
    cin>>s;
    s="*"+s;
    for(int j=1;j<=m;j++){
        if(s[j]=='A'){
            gr[i][j]=0;
        }
        if(s[j]=='C'){
            gr[i][j]=1;
        }
        if(s[j]=='G'){
            gr[i][j]=2;
        }
        if(s[j]=='T'){
            gr[i][j]=3;
        }
    }
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        ps[gr[i][j]][i][j]++;
        for(int k=0;k<4;k++){
            ps[k][i][j]+=ps[k][i-1][j];
        }
    }
}

}

int ok(int id){
int dif=0;
for(int i=1;i<=m;i++){
    dif+=n-ps[gr[id][i]][n][i];
}
if(dif!=K*(n-1)){return 0;}
for(int ttt=1;ttt<=30;ttt++){
    int pl=1+rnd()%n;
    dif=0;
    for(int i=1;i<=m;i++){
        dif+=pl-ps[gr[id][i]][pl][i];
    }
    if(dif!=K*pl-((pl>=id)*K) ){return 0;}
    dif=0;
    pl--;
    for(int i=1;i<=m;i++){
        dif+=(n-pl)-(ps[gr[id][i]][n][i]-ps[gr[id][i]][pl][i]);
    }
    if(dif!=K*(n-pl)-((pl<id)*K) ){return 0;}
}
for(int ttt=1;ttt<=30;ttt++){
    int pl=1+rnd()%n;
    if(pl==id){continue;}
    dif=0;
    for(int i=1;i<=m;i++){
        if(gr[id][i]!=gr[pl][i]){dif++;}
        if(dif>K){break;}
    }
    if(dif!=K){
        mby[pl]=-1;
        return 0;
    }
}
return 1;
}

int fchk(int id){

for(int pl=1;pl<=n;pl++){
    if(pl==id){continue;}
    int dif=0;
    for(int i=1;i<=m;i++){
        if(gr[id][i]!=gr[pl][i]){dif++;}
    }
    if(dif!=K){return 0;}
}
return 1;
}

signed main(){
init();
for(int i=1;i<=n;i++){
    if(mby[i]==-1){continue;}
    mby[i]=ok(i);
    /*if(mby[i]){
        cout<<i;return 0;
    }*/
}

int cnt=0;
for(int i=1;i<=n;i++){
    if(mby[i]==1){cnt++;}
}
assert(cnt<=100);
for(int i=1;i<=n;i++){
    if(mby[i]==1&&fchk(i)){
        cout<<i;return 0;
    }

}


}

Subtask #1
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 17240 KB Output is correct
2 Correct 3 ms 21336 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 18956 KB Output is correct
6 Correct 2 ms 17240 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 14936 KB Output is correct
10 Correct 2 ms 19036 KB Output is correct
11 Correct 3 ms 19036 KB Output is correct
12 Correct 3 ms 21084 KB Output is correct
13 Correct 3 ms 21084 KB Output is correct
14 Correct 3 ms 21084 KB Output is correct
15 Correct 3 ms 19292 KB Output is correct
16 Correct 3 ms 21084 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 246508 KB Output is correct
2 Correct 96 ms 293376 KB Output is correct
3 Correct 99 ms 279124 KB Output is correct
4 Correct 35 ms 187988 KB Output is correct
5 Correct 102 ms 293368 KB Output is correct
6 Correct 107 ms 294756 KB Output is correct
7 Correct 46 ms 128472 KB Output is correct
8 Correct 43 ms 127316 KB Output is correct
9 Correct 106 ms 281140 KB Output is correct
10 Correct 161 ms 282452 KB Output is correct
11 Correct 115 ms 246492 KB Output is correct
12 Correct 90 ms 248404 KB Output is correct
13 Correct 87 ms 247376 KB Output is correct
14 Correct 73 ms 214608 KB Output is correct
15 Runtime error 267 ms 392716 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 246508 KB Output is correct
2 Correct 96 ms 293376 KB Output is correct
3 Correct 99 ms 279124 KB Output is correct
4 Correct 35 ms 187988 KB Output is correct
5 Correct 102 ms 293368 KB Output is correct
6 Correct 107 ms 294756 KB Output is correct
7 Correct 46 ms 128472 KB Output is correct
8 Correct 43 ms 127316 KB Output is correct
9 Correct 106 ms 281140 KB Output is correct
10 Correct 161 ms 282452 KB Output is correct
11 Correct 115 ms 246492 KB Output is correct
12 Correct 90 ms 248404 KB Output is correct
13 Correct 87 ms 247376 KB Output is correct
14 Correct 73 ms 214608 KB Output is correct
15 Runtime error 267 ms 392716 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 17240 KB Output is correct
2 Correct 3 ms 21336 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 18956 KB Output is correct
6 Correct 2 ms 17240 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 14936 KB Output is correct
10 Correct 2 ms 19036 KB Output is correct
11 Correct 3 ms 19036 KB Output is correct
12 Correct 3 ms 21084 KB Output is correct
13 Correct 3 ms 21084 KB Output is correct
14 Correct 3 ms 21084 KB Output is correct
15 Correct 3 ms 19292 KB Output is correct
16 Correct 3 ms 21084 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 315 ms 246508 KB Output is correct
19 Correct 96 ms 293376 KB Output is correct
20 Correct 99 ms 279124 KB Output is correct
21 Correct 35 ms 187988 KB Output is correct
22 Correct 102 ms 293368 KB Output is correct
23 Correct 107 ms 294756 KB Output is correct
24 Correct 46 ms 128472 KB Output is correct
25 Correct 43 ms 127316 KB Output is correct
26 Correct 106 ms 281140 KB Output is correct
27 Correct 161 ms 282452 KB Output is correct
28 Correct 115 ms 246492 KB Output is correct
29 Correct 90 ms 248404 KB Output is correct
30 Correct 87 ms 247376 KB Output is correct
31 Correct 73 ms 214608 KB Output is correct
32 Runtime error 267 ms 392716 KB Execution killed with signal 6
33 Halted 0 ms 0 KB -