Submission #499137

#	Time	Username	Problem	Language	Result	Execution time	Memory
499137		LucaIlie	Mutating DNA (IOI21_dna)	C++17	100 / 100	39 ms	4912 KiB

dna

#include <iostream>

#define MAX_N 100000

using namespace std;

struct abc {
    int ab, ac, ba, bc, ca, cb;
} sp[MAX_N + 1];

void init( string a, string b ) {
    int i;

    for ( i = 0; i < a.size(); i++ ) {
        sp[i + 1].ab = sp[i].ab + (a[i] == 'A' && b[i] == 'T');
        sp[i + 1].ac = sp[i].ac + (a[i] == 'A' && b[i] == 'C');
        sp[i + 1].ba = sp[i].ba + (a[i] == 'T' && b[i] == 'A');
        sp[i + 1].bc = sp[i].bc + (a[i] == 'T' && b[i] == 'C');
        sp[i + 1].ca = sp[i].ca + (a[i] == 'C' && b[i] == 'A');
        sp[i + 1].cb = sp[i].cb + (a[i] == 'C' && b[i] == 'T');
    }
}

int get_distance( int x, int y ) {
    int ab, ac, ba, bc, ca, cb;

    y++;
    ab = sp[y].ab - sp[x].ab;
    ac = sp[y].ac - sp[x].ac;
    ba = sp[y].ba - sp[x].ba;
    bc = sp[y].bc - sp[x].bc;
    ca = sp[y].ca - sp[x].ca;
    cb = sp[y].cb - sp[x].cb;

    if ( ab + ac == ba + ca && ba + bc == ab + cb && ca + cb == ac + bc ) {
        int cost, x;

        cost = min( ab, ba ) + min( ac, ca ) + min( bc, cb );
        ab = abs( ab - ba );
        bc = abs( bc - cb );
        ca = abs( ac - ca );
        ba = cb = ac = 0;

        x = min( ab, bc );
        cost += x;
        ab -= x;
        bc -= x;
        ac += x;

        x = min( ac, ca );
        cost += x;
        ac -= x;
        ca -= x;

        return cost;
    }
    return -1;
}

Compilation message (stderr)

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

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