Submission #534580

#	Time	Username	Problem	Language	Result	Execution time	Memory
534580		__Variatto	Mutating DNA (IOI21_dna)	C++17	35 / 100	40 ms	6212 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"

using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=1e5+10;
int p12[MAX], p21[MAX],  p13[MAX], p31[MAX], p23[MAX], p32[MAX];
int get_distance(int x, int y){
    x++, y++;
    int i12=p12[y]-p12[x-1], i21=p21[y]-p21[x-1];
    int i13=p13[y]-p13[x-1], i31=p31[y]-p31[x-1];
    int i23=p23[y]-p23[x-1], i32=p32[y]-p32[x-1];

    int mini13=min(i13, i31);
    i13-=mini13, i31-=mini13;
    int mini12=min(i12, i21);
    i12=mini12, i21-=mini12;
    int mini23=min(i23, i32);
    i23=mini23, i32-=mini23;

    int i312=min(i13, min(i32, i21));
    i13-=i312, i32-=i312, i21-=i312;

    int i231=min(i12, min(i23, i31));
    i12-=i231, i23-=i231, i31-=i231;

    if(i12||i13||i21||i23||i32||i31)
        return -1;
    else
        return mini13+mini12+mini23+2*(i312+i231);
}
void init(string a, string b){
    int n=a.size();
    a='$'+a, b='$'+b;
    for(int i=1; i<=n; i++){
        p12[i]=p12[i-1], p21[i]=p21[i-1];
        p13[i]=p13[i-1], p31[i]=p31[i-1];
        p23[i]=p23[i-1], p32[i]=p32[i-1];
        if(a[i]=='A'&&b[i]=='C') p12[i]++;
        if(a[i]=='C'&&b[i]=='A') p21[i]++;
        if(a[i]=='C'&&b[i]=='T') p23[i]++;
        if(a[i]=='T'&&b[i]=='C') p32[i]++;
        if(a[i]=='A'&&b[i]=='T') p13[i]++;
        if(a[i]=='T'&&b[i]=='A') p31[i]++;
    }
}
/*int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>a>>b;

}*/

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