Submission #443266

#	Time	Username	Problem	Language	Result	Execution time	Memory
443266		arujbansal	Mutating DNA (IOI21_dna)	C++17	100 / 100	317 ms	69684 KiB

dna

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

const int MXN = 1e5 + 5, INF = 1e9 + 5;
map<pair<char, char>, int> cnt[MXN];
map<char, int> char_cnt[MXN];

void init(string a, string b) {
    int n = sz(a);

    for (int i = 0; i < n; i++) {
        cnt[i][make_pair(a[i], b[i])]++;
        cnt[i + 1] = cnt[i];

        char_cnt[i][a[i]]++;
        char_cnt[i][b[i]]--;
        char_cnt[i + 1] = char_cnt[i];
    }
}

int get_distance(int x, int y) {
    if (char_cnt[y]['A'] - (x > 0 ? char_cnt[x - 1]['A'] : 0) != 0) return -1;
    if (char_cnt[y]['T'] - (x > 0 ? char_cnt[x - 1]['T'] : 0) != 0) return -1;
    if (char_cnt[y]['C'] - (x > 0 ? char_cnt[x - 1]['C'] : 0) != 0) return -1;

    int AT = cnt[y][make_pair('A', 'T')] - (x > 0 ? cnt[x - 1][make_pair('A', 'T')] : 0);
    int TA = cnt[y][make_pair('T', 'A')] - (x > 0 ? cnt[x - 1][make_pair('T', 'A')] : 0);

    int AC = cnt[y][make_pair('A', 'C')] - (x > 0 ? cnt[x - 1][make_pair('A', 'C')] : 0);
    int CA = cnt[y][make_pair('C', 'A')] - (x > 0 ? cnt[x - 1][make_pair('C', 'A')] : 0);

    int TC = cnt[y][make_pair('T', 'C')] - (x > 0 ? cnt[x - 1][make_pair('T', 'C')] : 0);
    int CT = cnt[y][make_pair('C', 'T')] - (x > 0 ? cnt[x - 1][make_pair('C', 'T')] : 0);

    int ans = min(AT, TA) + min(AC, CA) + min(TC, CT);

    int first = max(AT, TA) - min(AT, TA);
    int second = max(AC, CA) - min(CA, AC);
    int third = max(TC, CT) - min(TC, CT);

    ans += 2 * (first + second + third) / 3;

    return ans;
}

// void solve() {
//     init("ATC", "TCA");
//     cout << get_distance(0, 2) << "\n";
// }

// signed main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(nullptr);

//     int TC = 1;
//     // cin >> TC;
//     while (TC--) solve();
// }

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