Submission #1244382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244382		vtnoo	Mutating DNA (IOI21_dna)	C++20	0 / 100	22 ms	4864 KiB

dna

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

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])continue;
        if(dir[{y[i], x[i]}]){
            p[i+1]++;
            dir.erase({y[i], x[i]});
            continue;
        }
        dir[{x[i], y[i]}]=i;
    }
}

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;
    }      
    int dom=p[y]-p[x-1];
    return dom+(((y-x+1)-dom*2)/3)*2;
}

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