Submission #534723

#	Time	Username	Problem	Language	Result	Execution time	Memory
534723		__Variatto	Mutating DNA (IOI21_dna)	C++17	100 / 100	45 ms	6308 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(i21, i32));
    i13-=i312, i21-=i312, i32-=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(){
    string a, b;
    cin>>a>>b;
    init(a, b);
    while(true){
        int x, y;
        cin>>x>>y;
        cout<<get_distance(x, y)<<"\n";

    }

}*/

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