Submission #1245214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245214		Minbaev	Mutating DNA (IOI21_dna)	C++20	100 / 100	151 ms	7028 KiB

dna

#include "dna.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define ar      array
#define mrand(a, b)   uniform_int_distribution<int>(a, b)(rng)

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace FAST {
    template<typename T, typename F>
    istream &operator>>(istream &cin, pair<T, F> &p) {
        cin >> p.first >> p.second;
        return cin;
    }

    template<typename T, typename F>
    ostream &operator<<(ostream &cout, pair<T, F> &p) {
        cout << p.first << ' ' << p.second;
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
    for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
          for (T i: a) cout << i << ' ';
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, deque<T> &a) {
        for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, deque<T> &a) {
        for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

const long long inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int md = 998244353;

string A, B;
vector<ar<int,3>>cnt(100005);
vector<int>g[100000];

int fborders(int a, int b, char x, char y){
    int num = (x - 'A' + 1) * 30 + (y - 'A' + 1);
    
    int l = 0, r = (int)g[num].size()-1, ans = -1;
    while(l <= r){
        int mid = (l + r) / 2;

        if(g[num][mid] >= a){
            r = mid - 1;
            ans = mid;
        }
        else l = mid + 1;
    }

    l = 0, r = (int)g[num].size()-1; int ans2 = -1;
    while(l <= r){
        int mid = (l + r) / 2;

        if(g[num][mid] <= b){
            l = mid + 1;
            ans2 = mid;
        }
        else r = mid - 1;
    }

    // cout << ans << " " << ans2 << " " << num << "\n";

    if(ans == -1 || ans2 == -1)return 0;
    return ans2 - ans + 1;
}

void init(string a, string b){
    A = a;
    B = b;

    for(int i = 0;i<A.size();i++){
        if(i > 0){
            cnt[i][0] = cnt[i-1][0];
            cnt[i][1] = cnt[i-1][1];
            cnt[i][2] = cnt[i-1][2];
        }
        cnt[i][0] += (A[i] == 'A') - (B[i] == 'A');
        cnt[i][1] += (A[i] == 'B') - (B[i] == 'B');
        cnt[i][2] += (A[i] == 'C') - (B[i] == 'C');
    }

    for(int i = 0;i<A.size();i++){
        int num = (A[i] - 'A' + 1) * 30 + (B[i] - 'A' + 1);
        g[num].pb(i);
    }
}

int get_distance(int x, int y) {

    int a = 0, b = 0, c = 0;
    if(x > 0){
        a = cnt[x-1][0];
        b = cnt[x-1][1];
        c = cnt[x-1][2];
    }

    if(!(cnt[y][0] - a == 0 && cnt[y][1] - b == 0 && cnt[y][2] - c == 0))return -1;

    int res = 0;
    
    int cnt = 0, cont = 0;

    cnt += min(fborders(x, y, 'A', 'T'), fborders(x, y, 'T', 'A'));
    cnt += min(fborders(x, y, 'A', 'C'), fborders(x, y, 'C', 'A'));
    cnt += min(fborders(x, y, 'C', 'T'), fborders(x, y, 'T', 'C'));

    cont += fborders(x, y, 'A', 'A');
    cont += fborders(x, y, 'C', 'C');
    cont += fborders(x, y, 'T', 'T');

    // for(auto to:g[91])cout << to << " ";
    // cout << "\n";
    
    // cout << fborders(x, y, 'A', 'C') << " " << fborders(x, y, 'C', 'A') << "\n";

    res = (y-x+1 - cnt*2 - cont) / 3 * 2;
    res += cnt;

    return res;
}

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