Submission #1062435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062435		TheQuantiX	Mutating DNA (IOI21_dna)	C++17	100 / 100	294 ms	88280 KiB

dna

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll n, m, q, k, x, y, a, b, c;
map<char, int> mpa[100001];
map<char, int> mpb[100001];
map< pair<char, char>, int > mp[100001];

void init(string a, string b) {
    for (int i = 0; i < a.size(); i++) {
        mp[i + 1] = mp[i];
        mp[i + 1][{a[i], b[i]}]++;
        mpa[i + 1] = mpa[i];
        mpb[i + 1] = mpb[i];
        mpa[i + 1][a[i]]++;
        mpb[i + 1][b[i]]++;
    }
}

int get_distance(int x, int y) {
    for (auto i : {'A', 'T', 'C'}) {
        // cout << i << ' ' << mpa[y + 1][i] - mpa[x][i] << ' ' << mpb[y + 1][i] - mpb[x][i] << '\n';
        if (mpa[y + 1][i] - mpa[x][i] != mpb[y + 1][i] - mpb[x][i]) {
            return -1;
        }
    }
    map< pair<char, char>, int > mp1;
    for (auto i : mp[y + 1]) {
        mp1[i.first] = i.second - mp[x][i.first];
    }
    int ans = 0;
    ll e;
    e = min(mp1[{'A', 'T'}], mp1[{'T', 'A'}]);
    ans += e;
    mp1[{'A', 'T'}] -= e;
    mp1[{'T', 'A'}] -= e;
    e = min(mp1[{'A', 'C'}], mp1[{'C', 'A'}]);
    ans += e;
    mp1[{'A', 'C'}] -= e;
    mp1[{'C', 'A'}] -= e;
    e = min(mp1[{'C', 'T'}], mp1[{'T', 'C'}]);
    ans += e;
    mp1[{'C', 'T'}] -= e;
    mp1[{'T', 'C'}] -= e;
    e = min({mp1[{'A', 'T'}], mp1[{'T', 'C'}], mp1[{'C', 'A'}]});
    ans += e * 2;
    mp1[{'A', 'T'}] -= e;
    mp1[{'T', 'C'}] -= e;
    mp1[{'C', 'A'}] -= e;
    e = min({mp1[{'T', 'A'}], mp1[{'C', 'T'}], mp1[{'A', 'C'}]});
    ans += e * 2;
    mp1[{'T', 'A'}] -= e;
    mp1[{'C', 'T'}] -= e;
    mp1[{'A', 'C'}] -= e;
    return ans;
}

Compilation message (stderr)

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