Submission #1062593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062593		DucNguyen2007	Genetics (BOI18_genetics)	C++14	100 / 100	279 ms	33872 KiB

genetics

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
mt19937 Rand(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxN=4105,MOD=1e9+7;
const ll inf=2e18;
int n,m,k;
ll Hash[maxN+1],f[maxN+1][4];
string s[maxN+1];
ll gen(ll MOD)
{
    return Rand()%MOD;
}
int cd(char c)
{
    if(c=='A')
    {
        return 0;
    }
    if(c=='C')
    {
        return 1;
    }
    if(c=='G')
    {
        return 2;
    }
    return 3;
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    ll base=0;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]=" "+s[i];
        Hash[i]=gen(MOD);
        base=(base+Hash[i])%MOD;
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int tmp=cd(s[j][i]);
            f[i][tmp]=(f[i][tmp]+Hash[j])%MOD;
        }
    }
    for(int i=1;i<=n;i++)
    {
        ll res=0;
        for(int j=1;j<=m;j++)
        {
            int tmp=cd(s[i][j]);
            ll cur=(base-f[j][tmp])%MOD;
            if(cur<0)
            {
                cur+=MOD;
            }
            res=(res+cur)%MOD;
            //cout<<i<<" "<<j<<" "<<cur<<" "<<f[j][1-tmp]<<'\n';
        }
        ll cur=(base-Hash[i]+MOD)%MOD;
        //cout<<res<<" "<<base<<'\n';
        if(res==(k*cur)%MOD)
        {
            cout<<i;
            return 0;
        }
    }
}

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