Submission #1243806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243806		vtnoo	Mutating DNA (IOI21_dna)	C++20	0 / 100	23 ms	5376 KiB

dna

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAXN=100005;
int N, p[MAXN], e[MAXN];
pair<int,int> a[MAXN], t[MAXN], c[MAXN];

void init(string x, string y){
    N=x.size();
    for(int i=0;i<N;i++){
        if(x[i]=='A'){
            a[i+1].first++;
        }else if(x[i]=='T'){
            t[i+1].first++;
        }else{
            c[i+1].first++;
        }
        if(y[i]=='A'){
            a[i+1].second++;
        }else if(y[i]=='T'){
            t[i+1].second++;
        }else{
            c[i+1].second++;
        }
    }
    for(auto &d:{a, t, c}){
        for(int i=1;i<=N;i++){
            d[i].first+=d[i-1].first;
            d[i].second+=d[i-1].second;
        }
    }
    for(int i=0;i<N;i++){
        if(x[i]==y[i]){
            e[i+1]++;
        }
    }
    map<pair<int,int>, int> mp;
    for(int i=0;i<N;i++){
        if(mp.count({y[i], x[i]})){
            p[i+1]++;
            mp.erase({y[i], x[i]});
            continue;
        }
        mp[{x[i], y[i]}]=i;
    }
    for(int i=1;i<=N;i++){
        e[i]+=e[i-1];
        p[i]+=p[i-1];
    }
}

int get_distance(int x, int y){
    x++;y++;
    int cnt_a=a[y].first-a[x-1].first;
    int cnt_a2=a[y].second-a[x-1].second;
    int cnt_t=t[y].first-t[x-1].first;
    int cnt_t2=t[y].second-t[x-1].second;
    int cnt_c=c[y].first-c[x-1].first;
    int cnt_c2=c[y].second-c[x-1].second;
    if(cnt_a!=cnt_a2||cnt_t!=cnt_t2||cnt_c!=cnt_c2){
        return -1;
    }
    return (p[y]-p[x])+(y-x+1)-(e[y]-e[x]);
}

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