Submission #499094

#	Time	Username	Problem	Language	Result	Execution time	Memory
499094		blue	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	10884 KiB

dna

#include "dna.h"
#include <string>
#include <map>
#include <vector>
#include <iostream>
using namespace std;

const int maxN = 100000;

map<char, int> M;
int N;
vector<int> A, B;

int ct[1+maxN][4][4];

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

    A = B = vector<int>(N+1, 0);

    M['A'] = 1;
    M['C'] = 2;
    M['T'] = 3;

    for(int i = 0; i < N; i++)
    {
        A[i+1] = M[a[i]];
        B[i+1] = M[b[i]];
    }

    for(int i = 1; i <= N; i++)
    {
        for(int j1 = 1; j1 <= 3; j1++)
        {
            for(int j2 = 1; j2 <= 3; j2++)
            {
                ct[i][j1][j2] = ct[i-1][j1][j2] + (A[i] == j1 && B[i] == j2);
            }
        }
    }
}

int get_distance(int x, int y)
{
	int X[4][4];
    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++)
        {
            X[i][j] = ct[(y+1)][i][j] - ct[(x+1) - 1][i][j];
        }

    int res = 0;

    for(int k = 1; k <= 3; k++)
    {
        if(X[k][1] + X[k][2] + X[k][3] != X[1][k] + X[2][k] + X[3][k]) return -1;
    }





    int mov12 = min(X[1][2], X[2][1]);
    res += 1*mov12;
    X[1][2] -= mov12;
    X[2][1] -= mov12;

    int mov23 = min(X[2][3], X[3][2]);
    res += 1*mov23;
    X[2][3] -= mov23;
    X[3][2] -= mov23;

    int mov31 = min(X[3][1], X[1][3]);
    res += 1*mov31;
    X[1][3] -= mov31;
    X[3][1] -= mov31;






    int mov123 = min(X[1][2], min(X[2][3], X[3][1]));
    res += 2*mov123;
    X[1][2] -= mov123;
    X[2][3] -= mov123;
    X[3][1] -= mov123;

    int mov321 = min(X[2][1], min(X[3][2], X[1][3]));
    res += 2*mov321;
    X[2][1] -= mov321;
    X[3][2] -= mov321;
    X[1][3] -= mov321;

    return res;
}

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