Submission #135677

#	Time	Username	Problem	Language	Result	Execution time	Memory
135677		Plurm	Genetics (BOI18_genetics)	C++11	46 / 100	2036 ms	20124 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
char dna[4200][4200];
bitset<4200> enc1[4200];
bitset<4200> enc2[4200];
int cnt[4200][4];
inline int getMask(int x){
    switch(x){
        case 'A':
        return 0;
        case 'T':
        return 1;
        case 'C':
        return 2;
        case 'G':
        return 3;
    }
}
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1; i <= n; i++){
        scanf("%s",dna[i]+1);
        for(int j = 1; j <= m; j++){
            cnt[j][getMask(dna[i][j])]++;
            if(dna[i][j] == 'A' || dna[i][j] == 'T'){
                enc1[i][j] = 0;
            }else{
                enc1[i][j] = 1;
            }
            if(dna[i][j] == 'A' || dna[i][j] == 'C'){
                enc2[i][j] = 0;
            }else{
                enc2[i][j] = 1;
            }
        }
    }
    vector<int> v;
    for(int i = 1; i <= n; i++){
        int diffcnt = 0;
        int ccnt = 0;
        int nx = i % n + 1;
        for(int j = 1; j <= m; j++){
            diffcnt += n - cnt[j][getMask(dna[i][j])];
            if(dna[i][j] != dna[nx][j]) ccnt++;
        }
        if(true){
            v.push_back(i);
        }
    }
    for(int i : v){
        bool ok = true;
        for(int o = 1; o <= n; o++){
            if(o == i) continue;
            int cur = ((enc1[i] ^ enc1[o]) | (enc2[i] ^ enc2[o])).count();
            if(cur != k){
                ok = false;
                break;
            }
        }
        if(ok){
            printf("%d\n",i);
            return 0;
        }
    }
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
genetics.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",dna[i]+1);
         ~~~~~^~~~~~~~~~~~~~~
genetics.cpp: In function 'int getMask(int)':
genetics.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 27 / 27
• Subtask 2: 19 / 19
• Subtask 3: 0 / 28
• Subtask 4: 0 / 26