Submission #1291714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291714		HoriaHaivas	Genetics (BOI18_genetics)	C++20	100 / 100	259 ms	20532 KiB

genetics

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

map<int,int> taken;
string s[4505];
int rndval[4505];
int coef[4505];
int sum[4][4505];
int sumhash[4][4505];
const int mod=1e9+7;

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,k,i,j,kek,totalsum,hashsum,normalsum,is;
    cin >> n >> m >> k;
    totalsum=0;
    for (i=1; i<=n; i++)
    {
        do
        {
            kek=range_rng(1,1e9);
        }
        while (taken[kek]);
        taken[kek]=1;
        rndval[i]=kek;
        cin >> s[i];
        for (j=0; j<s[i].size(); j++)
        {
            if (s[i][j]=='A')
            {
                sum[0][j+1]++;
                sumhash[0][j+1]+=rndval[i];
            }
            if (s[i][j]=='C')
            {
                sum[1][j+1]++;
                sumhash[1][j+1]+=rndval[i];
            }
            if (s[i][j]=='G')
            {
                sum[2][j+1]++;
                sumhash[2][j+1]+=rndval[i];
            }
            if (s[i][j]=='T')
            {
                sum[3][j+1]++;
                sumhash[3][j+1]+=rndval[i];
            }
        }
        totalsum+=rndval[i]*k;
    }
    for (i=1;i<=n;i++)
    {
         hashsum=0;
         normalsum=0;
         for (j=0;j<s[i].size();j++)
         {
              if (s[i][j]=='A')
              {
                  normalsum+=sum[1][j+1];
                  hashsum+=sumhash[1][j+1];
                  normalsum+=sum[2][j+1];
                  hashsum+=sumhash[2][j+1];
                  normalsum+=sum[3][j+1];
                  hashsum+=sumhash[3][j+1];
              }
              if (s[i][j]=='C')
              {
                  normalsum+=sum[0][j+1];
                  hashsum+=sumhash[0][j+1];
                  normalsum+=sum[2][j+1];
                  hashsum+=sumhash[2][j+1];
                  normalsum+=sum[3][j+1];
                  hashsum+=sumhash[3][j+1];
              }
              if (s[i][j]=='G')
              {
                  normalsum+=sum[0][j+1];
                  hashsum+=sumhash[0][j+1];
                  normalsum+=sum[1][j+1];
                  hashsum+=sumhash[1][j+1];
                  normalsum+=sum[3][j+1];
                  hashsum+=sumhash[3][j+1];
              }
              if (s[i][j]=='T')
              {
                  normalsum+=sum[0][j+1];
                  hashsum+=sumhash[0][j+1];
                  normalsum+=sum[1][j+1];
                  hashsum+=sumhash[1][j+1];
                  normalsum+=sum[2][j+1];
                  hashsum+=sumhash[2][j+1];
              }
         }
         if (normalsum==(n-1)*k && hashsum==(totalsum-rndval[i]*k))
         {
             is=i;
             break;
         }
    }
    cout << is;
    return 0;
}

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