Submission #1117959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117959		kh0i	Mutating DNA (IOI21_dna)	C++17	100 / 100	39 ms	8644 KiB

dna

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const int N = 1e5 + 3;

string c = "ATC";
vector<pair<char, char>> diff = {{'A', 'T'}, {'T', 'A'}, {'T', 'C'}, {'C', 'T'}, {'C', 'A'}, {'A', 'C'}};

int n;
int cnts[3][N], cntt[3][N];
int pdiff[6][N];

int get(int l, int r, int *p){
    return p[r] - p[l - 1];
}

void init(string s, string t){
    n = sz(s);
    s = ' ' + s, t = ' ' + t;
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j < 3; ++j){
            cnts[j][i] = cnts[j][i - 1] + (s[i] == c[j]);
            cntt[j][i] = cntt[j][i - 1] + (t[i] == c[j]);
        }
        pair<char, char> p = {s[i], t[i]};
        for(int j = 0; j < 6; ++j)
            pdiff[j][i] = pdiff[j][i - 1] + (diff[j] == p);
    }
}

int get_distance(int x, int y){
    ++x, ++y;
    for(int j = 0; j < 3; ++j)
        if(get(x, y, cnts[j]) != get(x, y, cntt[j]))
            return -1;

    vector<int> cnt(6, 0);
    for(int j = 0; j < 6; ++j)
        cnt[j] = get(x, y, pdiff[j]);
    int res = 0, rem = 0;
    for(int j = 0; j < 6; j += 2){
        int mn = min(cnt[j], cnt[j + 1]);
        res += mn;
        cnt[j] -= mn, cnt[j + 1] -= mn;
        rem += cnt[j] + cnt[j + 1];
    }
    res += rem / 3 * 2;
    return res;
}

// void solve(){
//     cin >> n >> q;
//     cin >> s >> t;
//     init();
//     while(q--){
//         int x, y;
//         cin >> x >> y;
//         cout << get_distance(x, y);
//     }
// }

// int32_t main() {
//     cin.tie(nullptr)->sync_with_stdio(0);
//     #define task "troll"
//     if(fopen(task".inp", "r")){
//         freopen(task".inp", "r", stdin);
//         freopen(task".out", "w", stdout);
//     }
//     int test = 1;
// //    cin >> test;
//     for(int i = 1; i <= test; ++i){
// //        cout << "Case #" << i << ": ";
//         solve();
//     }
//     #ifdef LOCAL
//         cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
//     #endif
//     return 0;
// }

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