Submission #476420

#	Time	Username	Problem	Language	Result	Execution time	Memory
476420		Mahmudul_Kabir	Mutating DNA (IOI21_dna)	C++17	100 / 100	58 ms	13304 KiB

dna

//#include "dna.h"

#include "bits/stdc++.h"

#define sp <<" "
#define el <<"\n"
#define S second
#define F first
#define pb push_back
#define all(ar) ar.begin(),ar.end() 
#define pii pair<int,int> 

 
using namespace std;
using ll = long long; 
using ld = long double;
 
const ll mod = 100000007;
const ll si = 100005;
const ll inf = 7000; 

ll po[si][3], pt[si][3],n; 
unordered_map<char,ll> hau = {{'A',0},{'T',1},{'C',2}}; 
ll sco[si][6]; 

ll typ(char a,char b){
    if(a == 'A' && b == 'T') return 0; 
    else if(a == 'A' && b == 'C') return 1; 
    else if(a == 'T' && b == 'A') return 2; 
    else if(a == 'T' && b == 'C') return 3; 
    else if(a == 'C' && b == 'A') return 4; 
    else return 5; 
}


void init(std::string a, std::string b){
    n = a.size(); 
    memset(po,0,sizeof(po)); memset(pt,0,sizeof(pt)); memset(sco,0,sizeof(sco)); 
    po[0][hau[a[0]]] += 1; pt[0][hau[b[0]]] += 1;
    if(a[0] != b[0]) sco[0][typ(a[0],b[0])] += 1; 
    for(ll i = 1; i < n; i++){
        for(ll j = 0; j < 3; j++){
            po[i][j] = po[i - 1][j]; 
            pt[i][j] = pt[i - 1][j];
            sco[i][j] = sco[i - 1][j]; 
        }
        for(int j = 3; j < 6; j++) sco[i][j] = sco[i - 1][j];
        po[i][hau[a[i]]] += 1;
        pt[i][hau[b[i]]] += 1; 
        if(a[i] != b[i]) sco[i][typ(a[i],b[i])] += 1; 
    }
    //for(int i = 0; i < n; i++,cout el) for(int j = 0; j < 6; j++) cout<<sco[i][j] sp;  
    return; 
}

ll get(ll x,ll y,ll i,bool t){
    ll ans = t ? pt[y][i] : po[y][i]; 
    if(x) ans -= t ? pt[x - 1][i] : po[x - 1][i]; 
    return ans;  
}

ll get(ll x,ll y,ll t){
    ll ans = sco[y][t]; 
    if(x) ans -= sco[x - 1][t]; 
    return ans; 
}

bool hobe(ll x,ll y){
    //cout<<get(x,y,0,0) sp<< get(x,y,0,1) sp<<get(x,y,1,0) sp<< get(x,y,1,1) sp<<get(x,y,2,0) sp<< get(x,y,2,1) el; 
    return (get(x,y,0,0) == get(x,y,0,1)) && (get(x,y,1,0) == get(x,y,1,1)) && (get(x,y,2,0) == get(x,y,2,1)); 
}

int get_distance(int x, int y) {
    if(!hobe(x,y)) return -1; 
    ll at = get(x,y,0), ac = get(x,y,1), ta = get(x,y,2), tc = get(x,y,3), ca = get(x,y,4), ct = get(x,y,5);
    //cout<<at sp<<ta sp<<tc sp<<ct sp<<ac sp<<ca el;  
    ll ans = 0,mtc,mac,mat = min(at,ta); at -= mat; ta -= mat; ans += mat; 
    mtc = min(tc,ct); tc -= mtc; ct -= mtc; ans += mtc; 
    mac = min(ac,ca); ac -= mac; ca -= mac; ans += mac; 
    ans += max(at,ta) + max(tc,ct); 
    return ans; 
}

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