Submission #789342

#	Time	Username	Problem	Language	Result	Execution time	Memory
789342		borisAngelov	Mutating DNA (IOI21_dna)	C++17	100 / 100	34 ms	9756 KiB

dna

#include <bits/stdc++.h>
//#include "grader.cpp"
#include "dna.h"

using namespace std;

const int maxn = 100005;

int n;

int preffix1[maxn][3];
int preffix2[maxn][3];

int preffix_state[maxn][3][3];

int to_number[256];

void init(string a, string b)
{
    n = a.size();

    to_number['A'] = 0;
    to_number['C'] = 1;
    to_number['T'] = 2;

    a = '#' + a;
    b = '#' + b;

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            preffix1[i][j] = preffix1[i - 1][j];
            preffix2[i][j] = preffix2[i - 1][j];
        }

        ++preffix1[i][to_number[a[i]]];
        ++preffix2[i][to_number[b[i]]];

        for (int x = 0; x < 3; ++x)
        {
            for (int y = 0; y < 3; ++y)
            {
                preffix_state[i][x][y] = preffix_state[i - 1][x][y];
            }
        }

        ++preffix_state[i][to_number[a[i]]][to_number[b[i]]];
    }
}

int curr_state[3][3];

int get_distance(int l, int r)
{
    ++l;
    ++r;

    for (int i = 0; i < 3; ++i)
    {
        if (preffix1[r][i] - preffix1[l - 1][i] != preffix2[r][i] - preffix2[l - 1][i])
        {
            return -1;
        }
    }

    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            curr_state[i][j] = preffix_state[r][i][j] - preffix_state[l - 1][i][j];
        }
    }

    curr_state[0][0] = 0;
    curr_state[1][1] = 0;
    curr_state[2][2] = 0;

    int ans = 0;

    for (int i = 0; i < 3; ++i)
    {
        for (int j = i + 1; j < 3; ++j)
        {
            int swaps = min(curr_state[i][j], curr_state[j][i]);
            ans += swaps;

            curr_state[i][j] -= swaps;
            curr_state[j][i] -= swaps;
        }
    }

    int new_swaps = 0;

    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            new_swaps += curr_state[i][j];
        }
    }

    return ans + (new_swaps * 2) / 3;
}

/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5

6 1
ATACAT
ACTATA
1 3

0 and 1 --> 0 1
0 and 2 --> 1 0
1 and 2 --> 0 1
*/

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:37:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |         ++preffix1[i][to_number[a[i]]];
      |                                     ^
dna.cpp:38:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   38 |         ++preffix2[i][to_number[b[i]]];
      |                                     ^
dna.cpp:48:42: warning: array subscript has type 'char' [-Wchar-subscripts]
   48 |         ++preffix_state[i][to_number[a[i]]][to_number[b[i]]];
      |                                          ^
dna.cpp:48:59: warning: array subscript has type 'char' [-Wchar-subscripts]
   48 |         ++preffix_state[i][to_number[a[i]]][to_number[b[i]]];
      |                                                           ^

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