Submission #599414

#	Time	Username	Problem	Language	Result	Execution time	Memory
599414		_petar_b	Mutating DNA (IOI21_dna)	C++17	100 / 100	125 ms	9736 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define MAXN 100010
#define pb push_back
#define ll long long
#define fi first
#define se second
#define mp make_pair

using namespace std;

int psum[3][3][MAXN], numofa[3][MAXN], numofb[3][MAXN];

int conv(char c)
{
    if (c == 'A') return 0;
    if (c == 'T') return 1;
    if (c == 'C') return 2;
}

void init(std::string a, std::string b)
{
    for (int i = 1; i <= a.size(); i++)
    {
        for (int j = 0; j < 3; j++)
        {
            numofa[j][i] = numofa[j][i-1];
            numofb[j][i] = numofb[j][i-1];
        }
        for (int j = 0; j < 3; j++)
            for (int p = 0; p < 3; p++)
                psum[j][p][i] = psum[j][p][i-1];
        psum[conv(a[i-1])][conv(b[i-1])][i]++;
        numofa[conv(a[i-1])][i]++;
        numofb[conv(b[i-1])][i]++;
    }
}

int get_distance(int x, int y)
{
    x++; y++;
    for (int i = 0; i < 3; i++)
    {
        if (numofa[i][y]-numofa[i][x-1] != numofb[i][y]-numofb[i][x-1])
            return -1;
    }
    int dist = 0;
    dist += min((psum[0][1][y]-psum[0][1][x-1]), (psum[1][0][y]-psum[1][0][x-1]));
    dist += min((psum[0][2][y]-psum[0][2][x-1]), (psum[2][0][y]-psum[2][0][x-1]));
    dist += min((psum[1][2][y]-psum[1][2][x-1]), (psum[2][1][y]-psum[2][1][x-1]));
    int diffAT, diffAC, diffTC;
    diffAT = abs((psum[0][1][y]-psum[0][1][x-1]) - (psum[1][0][y]-psum[1][0][x-1]));
    diffAC = abs((psum[0][2][y]-psum[0][2][x-1]) - (psum[2][0][y]-psum[2][0][x-1]));
    diffTC = abs((psum[1][2][y]-psum[1][2][x-1]) - (psum[2][1][y]-psum[2][1][x-1]));
    dist += (diffAT + diffAC + diffTC) / 3 * 2;
	return dist;
}

Compilation message (stderr)

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

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