Submission #968701

#	Time	Username	Problem	Language	Result	Execution time	Memory
968701		crazycoder00	Mutating DNA (IOI21_dna)	C++17	100 / 100	36 ms	9288 KiB

dna

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

// Templates
// ==============================================
    // Debugging
    #ifdef LOCAL
    #include "debug.h"
    #else
    #define debug(...)
    #endif

    typedef long long ll;
    typedef vector<int> VI;
    typedef vector<long long> VLL;
    typedef vector<bool> VB;
    typedef vector<vector<int>> VVI;
    typedef pair<int, int> PI;
    typedef pair<ll, ll> PLL;
    typedef vector<pair<int, int>> VPI;
    #define pb push_back
    #define ff first
    #define ss second
    #define loop(i, s, e) for (int i = s; i < e; ++i)
    #define inp(v) for (auto& x : v) cin >> x
    #define all(a) a.begin(), a.end()
    #define revall(a) a.rbegin(), a.rend()
    #define nl "\n"
    // #define MOD 998244353
    #define MOD 1000000007
    #define MAXN 300002
    #define INF (int) 1e9
    #define INFL (ll) 1e18
    #define yep cout << "YES\n"
    #define nope cout << "NO\n"
// ==============================================

#define AB 0
#define BC 1
#define CA 2
#define BA 3
#define CB 4
#define AC 5
#define get(l, r, x) pre[r + 1][x] - pre[l][x]

VVI pre;

void init(std::string a, std::string b)
{
    int n = a.size();
    pre.resize(n + 1, VI(6));

    loop(i, 0, n)
    {
        pre[i + 1][AB] = pre[i][AB] + (make_pair(a[i], b[i]) == make_pair('A', 'T'));
        pre[i + 1][AC] = pre[i][AC] + (make_pair(a[i], b[i]) == make_pair('A', 'C'));
        pre[i + 1][CB] = pre[i][CB] + (make_pair(a[i], b[i]) == make_pair('C', 'T'));
        pre[i + 1][BC] = pre[i][BC] + (make_pair(a[i], b[i]) == make_pair('T', 'C'));
        pre[i + 1][BA] = pre[i][BA] + (make_pair(a[i], b[i]) == make_pair('T', 'A'));
        pre[i + 1][CA] = pre[i][CA] + (make_pair(a[i], b[i]) == make_pair('C', 'A'));
    }
}

int get_distance(int x, int y)
{
    int cnt[6];
    loop(i, 0, 6) cnt[i] = get(x, y, i);

    int ans = 0;
    loop(i, 0, 3)
    {
        int mn = min(cnt[i], cnt[i + 3]);
        cnt[i] -= mn;
        cnt[i + 3] -= mn;

        ans += mn;
    }

    if (cnt[0] == cnt[1] && cnt[1] == cnt[2] && cnt[3] == cnt[4] && cnt[4] == cnt[5])
    {
        ans += 2 * max(cnt[0], cnt[3]);
        return ans;
    }
    else return -1;
}

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