Submission #1166797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166797		TsotneSV	Mutating DNA (IOI21_dna)	C++20	100 / 100	58 ms	33096 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋       
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

//const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=2e5+5; 
const ll inf=1e9,INF=1e18; 

int N;
vector<vector<vi>> pref;
vector<vi> pA,pB;

int encode(char c) {
    if(c == 'A') return 0;
    if(c == 'T') return 1;
    return 2;
}

void init(string a, string b) {

    N = a.size(); pref = vector<vector<vi>>(N+1,vector<vi>(3,vi(3,0))); pA = pB = vector<vi>(N+1,vi(3,0));

    for(int i=1;i<=N;i++) {
        for(int j=0;j<3;j++) {
            pA[i][j] = pA[i-1][j]; pB[i][j] = pB[i-1][j];
            for(int k=0;k<3;k++) {
                pref[i][j][k] = pref[i-1][j][k];
            }
        } pref[i][encode(a[i-1])][encode(b[i-1])]++; pA[i][encode(a[i-1])]++; pB[i][encode(b[i-1])]++;
    }

}

int get_distance(int x, int y) {
	
    int amount[3][3]; bool f = 1;

    for(int i=0;i<3;i++) {
        f &= ((pA[y+1][i] - pA[x][i]) == (pB[y+1][i] - pB[x][i]));
        for(int j=0;j<3;j++) {
            amount[i][j] = pref[y+1][i][j] - pref[x][i][j];
        }
    } int ans = 0;

    if(!f) return -1;

    for(int i=0;i<3;i++) {
        for(int j=0;j<3;j++) {

            if(i == j) continue;

            int mn = min(amount[i][j],amount[j][i]);
            ans += mn;
            amount[i][j] -= mn;
            amount[j][i] -= mn;
        }
    }

    int mx = 0;

    for(int i=0;i<3;i++) {
        for(int j=0;j<3;j++) {
            if(i == j) continue;
            mx = max(mx,amount[i][j]);
        }
    } ans += 2*mx;
    
    return ans;

}

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