Submission #828356

#	Time	Username	Problem	Language	Result	Execution time	Memory
828356		kamelfanger83	Mutating DNA (IOI21_dna)	C++17	100 / 100	38 ms	9152 KiB

dna

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> as[6], bs[6];

void init(string a, string b){
    for (int i = 0; i < 6; ++i) {
        as[i].assign(a.size(), 0);
        bs[i].assign(1, 0);
    }
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] == b[i]) continue;
        int f = 0, t = 0;
        if (a[i] == 'C') f = 1;
        if (b[i] == 'C') t = 1;
        if (a[i] == 'T') f = 2;
        if (b[i] == 'T') t = 2;
        if (f < t) t--;
        as[f * 2 + t][i] = 1;
    }
    for (int i = 0; i < a.size(); ++i) {
        for (int j = 0; j < 6; ++j) {
            bs[j].push_back(bs[j].back() + as[j][i]);
        }
    }
}

int get_distance(int x, int y){
    int graph [6];
    for (int i = 0; i < 6; ++i) {
        graph[i] = bs[i][y + 1] - bs[i][x];
    }
    if (graph[0] + graph[1] != graph[2] + graph[4]) return -1;
    if (graph[2] + graph[3] != graph[0] + graph[5]) return -1;
    if (graph[4] + graph[5] != graph[1] + graph[3]) return -1;
    int ans = 0;
    int AC = min(graph[0], graph[2]);
    ans += AC;
    graph[0] -= AC; graph[2] -= AC;
    int CT = min(graph[3], graph[5]);
    ans += CT;
    graph [3] -= CT; graph[5] -= CT;
    int TA = min(graph[4], graph[1]);
    ans += TA;
    graph[4] -= TA; graph[1] -= TA;
    if (graph[0]){
        int val = graph[0];
        ans += 2 * val;
    }
    else if (graph[1]){
        int val = graph[1];
        ans += 2 * val;
    }
    return ans;
}

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 < a.size(); ++i) {
      |                     ~~^~~~~~~~~~
dna.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int 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