Submission #757686

#	Time	Username	Problem	Language	Result	Execution time	Memory
757686		anaduguleanu	Mutating DNA (IOI21_dna)	C++17	100 / 100	53 ms	16008 KiB

dna

#include <iostream>
#include <cstring>
#include <map>
#include "dna.h"
#define MAX 100000
using namespace std;
int freqA1[MAX + 10], freqC1[MAX + 10], freqT1[MAX + 10], freqA2[MAX + 10], freqC2[MAX + 10], freqT2[MAX + 10], a[MAX + 10][5][5], aQuery[5][5];
map <char, int> mp;
void init(string s1, string s2)
{
    mp['A'] = 0;
    mp['C'] = 1;
    mp['T'] = 2;
    for (int i = 0; i < s1.size(); i++)
    {
        freqA1[i + 1] = freqA1[i] + (s1[i] == 'A');
        freqC1[i + 1] = freqC1[i] + (s1[i] == 'C');
        freqT1[i + 1] = freqT1[i] + (s1[i] == 'T');
        freqA2[i + 1] = freqA2[i] + (s2[i] == 'A');
        freqC2[i + 1] = freqC2[i] + (s2[i] == 'C');
        freqT2[i + 1] = freqT2[i] + (s2[i] == 'T');
        if (i >= 1)
            for (int ii = 0; ii <= 2; ii++)
                for (int jj = 0; jj <= 2; jj++)
                    a[i][ii][jj] = a[i - 1][ii][jj];
        a[i][mp[s1[i]]][mp[s2[i]]]++;
    }
}
int get_distance(int x, int y)
{
    if (freqA1[y + 1] - freqA1[x] != freqA2[y + 1] - freqA2[x])
        return -1;
    if (freqC1[y + 1] - freqC1[x] != freqC2[y + 1] - freqC2[x])
        return -1;
    if (freqT1[y + 1] - freqT1[x] != freqT2[y + 1] - freqT2[x])
        return -1;
    for (int i = 0; i <= 2; i++)
        for (int j = 0; j <= 2; j++)
        {
            aQuery[i][j] = a[y][i][j];
            if (x >= 1)
                aQuery[i][j] = aQuery[i][j] - a[x - 1][i][j];
        }
    long long ans1 = 0, ans2 = 0;
    for (int i = 0; i <= 2; i++)
        for (int j = 0; j <= 2; j++)
            if (i != j)
            {
                int minMoves = min(aQuery[i][j], aQuery[j][i]);
                ans1 = ans1 + minMoves;
                aQuery[i][j] = aQuery[i][j] - minMoves;
                aQuery[j][i] = aQuery[j][i] - minMoves;
                ans2 = ans2 + aQuery[i][j];
            }
    ans2 = ans2 * 2 / 3;
    return ans1 + ans2;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:14:23: 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 = 0; i < s1.size(); i++)
      |                     ~~^~~~~~~~~~~

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