Submission #1125933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125933		AverageAmogusEnjoyer	Genetics (BOI18_genetics)	C++20	100 / 100	290 ms	66412 KiB

genetics

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
    return ui(mrand);
}

const int N=4101;
int grid[N][N];
const int mod=1e9+7;
struct mi {
    int o;
    mi():o(0){}
    mi(ll _o) {
        o=int(_o%mod);
        if (o<0)
            o+=mod;
    }
    mi& operator+=(const mi &b) {
        if ((o+=b.o)>=mod) o -= mod;
        return *this;
    }
    mi& operator-=(const mi &b) {
        if ((o-=b.o)<0) o += mod;
        return *this;
    }
    mi& operator*=(const mi &b) {
        o=int(1LL*o*b.o%mod);
        return *this;
    }
    friend mi operator+(mi a,const mi &b) { return a += b; }
    friend mi operator-(mi a,const mi &b) { return a -= b; }
    friend mi operator*(mi a,const mi &b) { return a *= b; }
};
mi pref[N][4];
mi vals[N];
mi sum[N];
string S="ACGT";
string T;

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);

    int n,m,k;
    cin >> n >> m >> k;
    for (int i=0;i<n;i++) {
        cin >> T;
        for (int j=0;j<m;j++) {
            grid[i][j]=find(S.begin(),S.end(),T[j])-S.begin();
        }
    }
    mi W=0;
    for (int i=0;i<n;i++) 
        vals[i]=rng(),W+=vals[i];
    
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            sum[i]+=pref[j][0]+pref[j][1]+pref[j][2]+pref[j][3]-pref[j][grid[i][j]];
            pref[j][grid[i][j]]+=vals[i];
        }
    }
    for (int i=0;i<N;i++)
        for (int z=0;z<4;z++)
            pref[i][z]=0;
    for (int i=n-1;i>=0;i--) {
        for (int j=0;j<m;j++) {
            sum[i]+=pref[j][0]+pref[j][1]+pref[j][2]+pref[j][3]-pref[j][grid[i][j]];
            pref[j][grid[i][j]]+=vals[i];
        }
    }
    for (int i=0;i<n;i++) {
        if (sum[i].o==((W-vals[i])*k).o) {
            cout << i + 1 << "\n";
            return 0;
        }
    }

}

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