Submission #566333

#	Time	Username	Problem	Language	Result	Execution time	Memory
566333		hoanghq2004	Genetics (BOI18_genetics)	C++14	100 / 100	475 ms	19796 KiB

genetics

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 5010;
const int mod = 1e9 + 7;
const int base = 9450;

int n, m, k;
string s[N];
int code[256];
int power[N];
int H[N][4];

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    code['A'] = 0, code['C'] = 1, code['G'] = 2, code['T'] = 3;

    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) cin >> s[i];
    power[0] = 1;
    for (int i = 1; i < n; ++i) power[i] = 1LL * power[i - 1] * base % mod;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            H[j][code[s[i][j]]] += power[i];
            if (H[j][code[s[i][j]]] >= mod) H[j][code[s[i][j]]] -= mod;
        }
    }
    int tot = 0;
    for (int i = 0; i < n; ++i) tot = (tot + power[i]) % mod;
    for (int i = 0; i < n; ++i) {
        int T = 1LL * ((tot - power[i] + mod) % mod) * k % mod;
        int cur = 0;
        for (int j = 0; j < m; ++j) {
            for (int c = 0; c < 4; ++c)
                if (code[s[i][j]] != c) {
                    cur += H[j][c];
                    if (cur >= mod) cur -= mod;
                }
        }
        if (cur == T) {
            cout << i + 1;
            exit(0);
        }
    }
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:33:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   33 |             H[j][code[s[i][j]]] += power[i];
      |                              ^
genetics.cpp:34:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   34 |             if (H[j][code[s[i][j]]] >= mod) H[j][code[s[i][j]]] -= mod;
      |                                  ^
genetics.cpp:34:62: warning: array subscript has type 'char' [-Wchar-subscripts]
   34 |             if (H[j][code[s[i][j]]] >= mod) H[j][code[s[i][j]]] -= mod;
      |                                                              ^
genetics.cpp:44:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |                 if (code[s[i][j]] != c) {
      |                                 ^

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