Submission #477676

#	Time	Username	Problem	Language	Result	Execution time	Memory
477676		TairitsuOwO	Mutating DNA (IOI21_dna)	C++17	35 / 100	55 ms	9672 KiB

dna

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

const int mxn=1e5+9;
int counta[mxn][3], countb[mxn][3], arr[mxn][3][3];

void init(string a, string b) {
    auto f=[](char c)->int{
        return c=='A'? 0: c=='T'? 1: 2;
    };
    a=" "+a, b=" "+b;
    for (int i=1; i<a.length(); i++){
        for (int j=0; j<3; j++) for (int k=0; k<3; k++){
            arr[i][j][k]=arr[i-1][j][k];
            counta[i][j]=counta[i-1][j];
            countb[i][j]=countb[i-1][j];
        }
        counta[i][f(a[i])]++;
        countb[i][f(b[i])]++;
        arr[i][f(a[i])][f(b[i])]++;
    }
}

int get_distance(int x, int y) {
    x++, y++;
    for (int i=0; i<3; i++) if (counta[y][i]-counta[x-1][i]!=countb[y][i]-countb[x-1][i]) return -1;
    int tmp[3][3], res=0;
    for (int i=0; i<3; i++) for (int j=0; j<3; j++) tmp[i][j]=arr[y][i][j]-arr[x-1][i][j];
    for (int i=0; i<3; i++) for (int j=i+1; j<3; j++){
        int swaps=min(tmp[i][j], tmp[j][i]);
        tmp[i][j]-=swaps, tmp[j][i]-=swaps, res+=swaps;
    }
    for (int i=0; i<3; i++) for (int j=i+1; j<3; j++) res+=tmp[i][j];
	return res;
}

Compilation message (stderr)

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

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