Submission #566231

#	Time	Username	Problem	Language	Result	Execution time	Memory
566231		BJoozz	Genetics (BOI18_genetics)	C++17	100 / 100	574 ms	49944 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
#define int long long
void maxx(int &a,int b){if(b>a) a=b;}
void minn(int &a,int b){if(b<a) a=b;}
mt19937 rng(time(0));
int randint(int l,int r){
    return uniform_int_distribution < int > (l,r) (rng);
}
using ll = long long;
using ii = pair < int , int >;
const int MAX=4100+3,inf=1e9,mod=1e9+7;
using ld = long double;
short a[MAX][MAX];
int C[4][MAX];
int cs[300];
bool vs[MAX];
bool liv[MAX];
signed main(){
    //freopen("Genetics.inp","r",stdin);freopen("Genetics.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cs['A']=0;cs['C']=1;cs['G']=2;cs['T']=3;
    int n,m,K;
    cin>>n>>m>>K;
    string s;
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int j=1;j<=m;j++){
            a[i][j]=cs[s[j-1]];
        }
    }
    //int Q=14;
    while(1){
        int cn=0;
        memset(vs,0,sizeof vs);
        memset(C,0,sizeof C);
        for(int i=1;i<=n;i++)if(randint(0,1)==1){
            cn++;vs[i]=1;
            for(int j=1;j<=m;j++)
                C[a[i][j]][j]++;
        }

        int ans=0;
        int dem=0;
        for(int i=1;i<=n;i++)if(!liv[i]){
            int res=0;
            for(int j=1;j<=m;j++)
                res+=C[a[i][j]][j];
            res=cn*m-res;
            if(vs[i]) res+=K;
            if(res!=cn*K) liv[i]=1;
            dem++;
        }
        if(dem==1) break;
    }
    for(int i=1;i<=n;i++)if(!liv[i]){
        cout<<i;return 0;
    }
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:32:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   32 |             a[i][j]=cs[s[j-1]];
      |                              ^
genetics.cpp:46:13: warning: unused variable 'ans' [-Wunused-variable]
   46 |         int ans=0;
      |             ^~~

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