Submission #697756

#	Time	Username	Problem	Language	Result	Execution time	Memory
697756		hiikunZ	Mutating DNA (IOI21_dna)	C++17	0 / 100	36 ms	8260 KiB

dna

#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
vector<ll> X(200000,0),Y(200000,0),Z(200000,0);
void init(string a, string b){
    ll N = (ll)a.size();
    for(ll i = 0;i < N;i++){
        X[i + 1] = X[i];
        if(a[i] == b[i]){
            X[i + 1]++;
        }
        Y[i + 1] = Y[i];
        Z[i + 1] = Z[i];
        if(a[i] == 'A') Y[i + 1] = (Y[i + 1] + 12345678) % 998244353;
        if(a[i] == 'T') Y[i + 1] = (Y[i + 1] + 87654321) % 998244353;
        if(a[i] == 'C') Y[i + 1] = (Y[i + 1] + 14725836) % 998244353;
        if(b[i] == 'A') Z[i + 1] = (Z[i + 1] + 12345678) % 998244353;
        if(b[i] == 'T') Z[i + 1] = (Z[i + 1] + 87654321) % 998244353;
        if(b[i] == 'C') Z[i + 1] = (Z[i + 1] + 14725836) % 998244353;
    }
}
int get_distance(int x, int y){
    x--;
    if(Y[y] - Y[x] != Z[y] - Z[x]) return -1;
    ll ans = (1 + (y - x - (X[y] - X[x]))) / 2;
    return ans;
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16