Submission #1071322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071322		Kipras	Mutating DNA (IOI21_dna)	C++17	100 / 100	42 ms	11024 KiB

dna

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

//#include "dna.h"

const ll maxN = 1e5+10;

ll pref[maxN][3][3];

ll gt(char a) {
    if(a=='A')return 0;
    if(a=='T')return 1;
    return 2;
}

void init(string a, string b) {
    ll n=a.size();
    for(int i = 0; i < maxN; i++) for(int x = 0; x < 3; x++)for(int z = 0; z < 3; z++)pref[i][x][z]=0;
    for(int i = 1; i <= n; i++) {
        ll v1 = gt(a[i-1]), v2=gt(b[i-1]);
        for(int x = 0; x < 3; x++)for(int z = 0; z < 3; z++) pref[i][x][z]=pref[i-1][x][z];
        pref[i][v1][v2]++;
    }
}

int get_distance(int ind1, int ind2) {
    ll res=0;
    ll vals[3][3];
    ll a = 0, b = 0, c = 0;
    ll aa = 0, bb = 0, cc = 0;
    for(int i = 0; i < 3; i++)for(int x = 0; x < 3; x++)vals[i][x]=pref[ind2+1][i][x]-pref[ind1][i][x];
    for(int i = 0; i < 3; i++)for(int x = 0; x < 3; x++) {
        if(i==0) {
            a+=vals[i][x];
        }
        else if(i==1) {
            b+=vals[i][x];
        }
        else if(i==2) {
            c+=vals[i][x];
        }
        if(x==0) {
            aa+=vals[i][x];
        }
        else if(x==1) {
            bb+=vals[i][x];
        }
        else if(x==2) {
           cc+=vals[i][x];
        }
    }
    if(a!=aa||b!=bb||c!=cc) {
        return -1;
    }

    for(int i = 0; i < 3; i++)for(int x = i+1; x < 3; x++) {
        ll mn = min(vals[i][x], vals[x][i]);
        vals[i][x]-=mn;vals[x][i]-=mn;
        res+=mn;
    }
    res+=2*(vals[0][2]+vals[0][1]);

    return res;
}

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