Submission #1139057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139057		anmattroi	Mutating DNA (IOI21_dna)	C++17	100 / 100	59 ms	7332 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;

int n;
int sa[maxn], st[maxn], sc[maxn];
int ta[maxn], tt[maxn], tc[maxn];
int s[maxn][6];

void init(string a, string b) {
    n = a.size();
    a = "0" + a; b = "0" + b;
    for (int i = 1; i <= n; i++) {
        sa[i] = sa[i-1] + (a[i] == 'A'); ta[i] = ta[i-1] + (b[i] == 'A');
        st[i] = st[i-1] + (a[i] == 'T'); tt[i] = tt[i-1] + (b[i] == 'T');
        sc[i] = sc[i-1] + (a[i] == 'C'); tc[i] = tc[i-1] + (b[i] == 'C');
    }
    for (int i = 1; i <= n; i++) {
        s[i][0] = s[i-1][0];
        if (a[i] == 'A' && b[i] == 'C') ++s[i][0];
    }
    for (int i = 1; i <= n; i++) {
        s[i][1] = s[i-1][1];
        if (a[i] == 'T' && b[i] == 'A') ++s[i][1];
    }
    for (int i = 1; i <= n; i++) {
        s[i][2] = s[i-1][2];
        if (a[i] == 'C' && b[i] == 'T') ++s[i][2];
    }
    for (int i = 1; i <= n; i++) {
        s[i][3] = s[i-1][3];
        if (a[i] == 'C' && b[i] == 'A') ++s[i][3];
    }
    for (int i = 1; i <= n; i++) {
        s[i][4] = s[i-1][4];
        if (a[i] == 'A' && b[i] == 'T') ++s[i][4];
    }
    for (int i = 1; i <= n; i++) {
        s[i][5] = s[i-1][5];
        if (a[i] == 'T' && b[i] == 'C') ++s[i][5];
    }
}

//A-C 0 | C-A 3
//T-A 1 | A-T 4
//C-T 2 | T-C 5

int get_distance(int x, int y) {
    ++x; ++y;
    if (sa[y]-sa[x-1] != ta[y]-ta[x-1]) return -1;
    if (st[y]-st[x-1] != tt[y]-tt[x-1]) return -1;
    if (sc[y]-sc[x-1] != tc[y]-tc[x-1]) return -1;

    int AC = s[y][0]-s[x-1][0], CA = s[y][3]-s[x-1][3];
    int TA = s[y][1]-s[x-1][1], AT = s[y][4]-s[x-1][4];
    int CT = s[y][2]-s[x-1][2], TC = s[y][5]-s[x-1][5];
    if (AC == CA) {
        assert(TA == AT && CT == TC);
        return AC + TA + CT;
    }
    if (AC > CA) {
        int p = AC-CA;
        assert(TA-AT == p && CT-TC == p);
        return CA + AT + TC + 2 * p;
    }
    if (AC < CA) {
        int p = CA-AC;
        assert(AT-TA == p && TC-CT == p);
        return AC + TA + CT + 2 * p;
    }
	return 0;
}

/*
6 1
ATACAT
ACTATA

/*
6 1
ATACAT
ACTATA
1 3

*/

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