Submission #977852

#	Time	Username	Problem	Language	Result	Execution time	Memory
977852		efedmrlr	Genetics (BOI18_genetics)	C++17	100 / 100	813 ms	25628 KiB

genetics

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("bmi,avx2,popcnt")
#include <bits/stdc++.h>

#define int long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.begin(), x.end()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 4102;
const int INF = 1e9 + 500;
const int MOD = 1e13;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}
array<array<bitset<N>, N>, 4> s;
array<int, N> val;
array<array<int, N>, 4> sum;
vector<int> w(N, 0);
int n, m, k; 
void solve() {   
    cin >> n >> m >> k;
    int S = 0;
    REP(i, n) {
        w[i] = rng(); 
        w[i] %= MOD;
        // cout << w[i] << " \n";
        S += w[i];
        S %= MOD;
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            char t;
            cin >> t;
            s[0][i][j] = (t == 'A');
            s[1][i][j] = (t == 'C');
            s[2][i][j] = (t == 'G');
            s[3][i][j] = (t == 'T');
        }
    }
    REP(z, 4) {
        REP(i, m) sum[z][i] = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(s[z][i][j]) {
                    sum[z][j] += w[i];
                    sum[z][j] %= MOD;
                } 
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(!s[z][i][j]) continue;
                int x = sum[z][j] - w[i];
                if(x < 0) x+= MOD;
                val[i] += x;
                val[i] %= MOD;
            }
        } 

    }
    REP(i, n) {
        int sx = S - w[i];
        if(sx < 0) sx+= MOD;
        int x = sx * (m - k);
        x %= MOD;
        // cout << "i:" << i << " sx " << sx << " x:" << x << "\n";
        if(x == val[i]) {
            cout << i + 1 << "\n";
            return;
        }
        
    }
}

signed main() {
    fastio();
    solve();
}

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