Submission #1107046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107046		SulA	Mutating DNA (IOI21_dna)	C++17	100 / 100	37 ms	7540 KiB

dna

#include <bits/stdc++.h>
#define bitcount __builtin_popcountll
#define all(a) (a).begin(), (a).end()
#define pair(arg1, arg2) make_pair(arg1, arg2)
#pragma GCC optimize("O3,fast-math")
using namespace std;
using namespace std::chrono;

int ind(char c) {
    return c == 'A' ? 0 : (c == 'C' ? 1 : 2);
}
enum {
    A, C, T
};
struct info {
    int a[3][3];
    info() {
        memset(a, 0, sizeof a);
    }
    void add(char s, char t) {
        a[ind(s)][ind(t)]++;
    }
    friend info operator+ (info x, info y) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                x.a[i][j] += y.a[i][j];
            }
        }
        return x;
    }
    friend info operator- (info x, info y) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                x.a[i][j] -= y.a[i][j];
            }
        }
        return x;
    }
    int calc() {
        auto b = a;
        int ans = 0;

        int mn = min(b[A][C], b[C][A]);
        ans += mn;
        b[A][C] -= mn, b[C][A] -= mn;

        mn = min(b[C][T], b[T][C]);
        ans += mn;
        b[C][T] -= mn, b[T][C] -= mn;

        mn = min(b[A][T], b[T][A]);
        ans += mn;
        b[A][T] -= mn, b[T][A] -= mn;

        if (b[A][C] != b[C][T] || b[C][T] != b[T][A]) return -1;
        ans += 2*b[A][C];
        if (b[C][A] != b[A][T] || b[A][T] != b[T][C]) return -1;
        ans += 2*b[C][A];
        return ans;
    }
};

vector<info> pref;
void init(string s, string t) {
    pref.resize(s.size());
    pref[0].add(s[0], t[0]);
    for (int i = 1; i < s.size(); i++) {
        pref[i] = pref[i-1];
        pref[i].add(s[i], t[i]);
    }
}

int get_distance(int x, int y) {
    info p = pref[y];
    if (x > 0) p = p - pref[x-1];
    return p.calc();
}

Compilation message (stderr)

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

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