Submission #712500

#	Time	Username	Problem	Language	Result	Execution time	Memory
712500		Kripton	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	8648 KiB

dna

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

int a1[100001], a2[100001];
int c1[100001], c2[100001];
int t1[100001], t2[100001];
int difat[100001], difta[100001];
int difac[100001], difca[100001];
int diftc[100001], difct[100001];

void init(string a, string b)
{
    for(int i = 1; i <= a.size(); i++)
    {
        c1[i] = c1[i - 1] + (a[i - 1] == 'C');
        a1[i] = a1[i - 1] + (a[i - 1] == 'A');
        t1[i] = t1[i - 1] + (a[i - 1] == 'T');
        c2[i] = c2[i - 1] + (b[i - 1] == 'C');
        a2[i] = a2[i - 1] + (b[i - 1] == 'A');
        t2[i] = t2[i - 1] + (b[i - 1] == 'T');
        difat[i] = difat[i - 1] + (a[i - 1] == 'A' && b[i - 1] == 'T');
        difta[i] = difta[i - 1] + (a[i - 1] == 'T' && b[i - 1] == 'A');
        difac[i] = difac[i - 1] + (a[i - 1] == 'A' && b[i - 1] == 'C');
        difca[i] = difca[i - 1] + (a[i - 1] == 'C' && b[i - 1] == 'A');
        difct[i] = difct[i - 1] + (a[i - 1] == 'C' && b[i - 1] == 'T');
        diftc[i] = diftc[i - 1] + (a[i - 1] == 'T' && b[i - 1] == 'C');
    }
}

int get_distance(int x, int y)
{
    x++;
    y++;
    if(c1[y] - c1[x - 1] != c2[y] - c2[x - 1])
        return -1;
    if(a1[y] - a1[x - 1] != a2[y] - a2[x - 1])
        return -1;
    if(t1[y] - t1[x - 1] != t2[y] - t2[x - 1])
        return -1;
    int rez = 0, mini;
    int at = difat[y] - difat[x - 1], ta = difta[y] - difta[x - 1];
    mini = min(at, ta);
    rez += mini;
    at -= mini;
    ta -= mini;
    int ac = difac[y] - difac[x - 1], ca = difca[y] - difca[x - 1];
    mini = min(ac, ca);
    rez += mini;
    ac -= mini;
    ca -= mini;
    int tc = diftc[y] - diftc[x - 1], ct = difct[y] - difct[x - 1];
    mini = min(tc, ct);
    rez += mini;
    tc -= mini;
    ct -= mini;
    return rez + (at + ta + ac + ca + tc + ct) / 3 * 2;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:14:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i = 1; i <= a.size(); i++)
      |                    ~~^~~~~~~~~~~

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