Submission #759439

#	Time	Username	Problem	Language	Result	Execution time	Memory
759439		drdilyor	Mutating DNA (IOI21_dna)	C++17	100 / 100	44 ms	7632 KiB

dna

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

const int A = 0, B = 1, C = 2;
vector<array<array<int, 3>,3>> cnt;
string a, b;
void init(std::string a, std::string b) {
    ::a = a, ::b = b;
    map<char,int> code;
    code['C'] = A;
    code['T'] = B;
    code['A'] = C;
    cnt.resize(a.size());
    for (int i = 0; i < int(a.size()); i++) {
        if (i) cnt[i] = cnt[i-1];
        cnt[i][code[a[i]]][code[b[i]]]++;
    }
}

int get_distance(int x, int y) {
    decltype(cnt)::value_type c = cnt[y];
    if (x) {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                c[i][j] -= cnt[x-1][i][j];
    }
    //for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) cout << i<<':'<<j<<':' << c[i][j] << endl;

    int res = 0;
    for (int i : {A, B, C}) {
        c[i][i] = 0;
        for (int j : {A, B, C}) {
            if (i == j) continue;
            int resolve = min(c[i][j], c[j][i]);
            c[i][j] -= resolve;
            c[j][i] -= resolve;
            res += resolve;
            for (int k : {A, B, C}) {
                if (k == i || k == j) continue;
                int resolve = min({c[i][j], c[j][k], c[k][i]});
                c[i][j] -= resolve;
                c[j][k] -= resolve;
                c[k][i] -= resolve;
                res += resolve * 2;
            }
        }
    }
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (c[i][j]) return -1;
	return res;
}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:50:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   50 |     for (int i = 0; i < 3; i++)
      |     ^~~
dna.cpp:53:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   53 |  return res;
      |  ^~~~~~

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