Submission #542045

#	Time	Username	Problem	Language	Result	Execution time	Memory
542045		Vladth11	Mutating DNA (IOI21_dna)	C++17	100 / 100	230 ms	17960 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 100001;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 1000000;
const ll nr_of_bits = 16;

struct mat{
    int wrong[3][3];
    void clear(){
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++)
                wrong[i][j] = 0;
        }
    }
};

class AINT {
    public:
    mat aint[4 * NMAX];
    mat combine(mat a, mat b) {
        mat sol;
        sol.clear();
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                sol.wrong[i][j] = a.wrong[i][j] + b.wrong[i][j];
            }
        }
        return sol;
    }
    void update(int node, int st, int dr, int poz, int a, int b) {
        aint[node].wrong[a][b]++;
        if(st == dr) {
            return;
        }
        int mid = (st + dr) / 2;
        if(poz <= mid)
            update(node * 2, st, mid, poz, a, b);
        else
            update(node * 2 + 1, mid + 1, dr, poz, a, b);
    }
    mat query(int node, int st, int dr, int a, int b) {
        if(a <= st && dr <= b) {
            return aint[node];
        }
        int mid = (st + dr) / 2;
        mat sol;
        sol.clear();
        if(a <= mid)
            sol = combine(sol, query(node * 2, st, mid, a, b));
        if(b > mid)
            sol = combine(sol, query(node * 2 + 1, mid + 1, dr, a, b));
        return sol;
    }
}st;

int n;

int getCode(char c){
    if(c == 'A')
        return 0;
    else if(c == 'C')
        return 1;
    return 2;
}

void init(std::string a, std::string b) {
    n = a.size();
    for(int i = 0; i < 4 * NMAX; i++)
        st.aint[i].clear();
    for(int i = 0; i < a.size(); i++){
        int codA = getCode(a[i]);
        int codB = getCode(b[i]);
        if(codA != codB)
            st.update(1, 1, n, i + 1, codA, codB);
    }
}

int get_distance(int x, int y) {
    x++;
    y++;
    mat my = st.query(1, 1, n, x, y);
    for(int i = 0; i < 3; i++){
        int s = 0;
        for(int j = 0; j < 3; j++){
            s += my.wrong[i][j];
        }
        for(int j = 0; j < 3; j++){
            s -= my.wrong[j][i];
        }
        if(s != 0){
            return -1;
        }
    }
    int cnt = 0;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            int minim = min(my.wrong[j][i], my.wrong[i][j]);
            my.wrong[j][i] -= minim;
            my.wrong[i][j] -= minim;
            cnt += minim;
        }
    }
    int s = 0;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            s += my.wrong[i][j];
        }
    }
    s /= 3;
    s *= 2;
    cnt += s;
    return cnt;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     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