제출 #1097854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097854		TheSahib	Genetics (BOI18_genetics)	C++14	100 / 100	676 ms	40020 KiB

genetics

#include <bits/stdc++.h>

#define ll long long
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const long long oo = 1e18;
const int MAX = 1e5 + 5;
const int BASE1 = 91, BASE2 = 101, MOD = 1e9 + 7;

int pw1[MAX], pw2[MAX];

int n, m, k;
vector<string> arr;
map<char, int> mp = {{'A', 'A'}, {'C', 'B'}, {'G', 'C'}, {'T', 'D'}};

pair<int, int> S[MAX][4];
void solve(){
    cin >> n >> m >> k;
    arr.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        for(char& c:arr[i]){
            c = mp[c];
        }
    }
    for(int j = 0; j < m; ++j){
        for(int i = 0; i < n; ++i){
            for(int k = 0; k < 4; ++k){
                if(k != (arr[i][j] - 'A')){
                    S[j][k] = {(S[j][k].first + pw1[i]) % MOD, (S[j][k].second + pw2[i]) % MOD};
                }
            }
        }
    }
    pair<int, int> H = {0, 0};
    for (int i = 0; i < n; i++)
    {
        H = {(H.first + pw1[i] * k) % MOD, H.second + pw2[i] * k};
    }
    for(int i = 0; i < n; ++i){
        H = {((H.first - pw1[i] * k) % MOD + 2 * MOD) % MOD,
             ((H.second - pw2[i] * k) % MOD + 2 * MOD) % MOD};
        pair<int, int> tmp = {0, 0};
        for(int j = 0; j < m; ++j){
            tmp.first = (tmp.first + S[j][arr[i][j] - 'A'].first) % MOD;
            tmp.second = (tmp.second + S[j][arr[i][j] - 'A'].second) % MOD;
        }
        if(tmp == H){
            cout << i + 1 << '\n';
            return;
        }
        H = {((H.first + pw1[i] * k)) % MOD,
             ((H.second + pw2[i] * k)) % MOD};
    }
}

signed main()
{
    pw1[0] = 1;
    for(int i = 1; i < MAX; ++i){
        pw1[i] = (pw1[i - 1] * BASE1) % MOD;
    }
    pw2[0] = 1;
    for(int i = 1; i < MAX; ++i){
        pw2[i] = (pw2[i - 1] * BASE2) % MOD;
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t){
        t--;
        solve();
    }
}

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