Submission #485648

#	Time	Username	Problem	Language	Result	Execution time	Memory
485648		niloyroot	Mutating DNA (IOI21_dna)	C++17	100 / 100	65 ms	14348 KiB

dna

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pl = pair<ll,ll>;
#define pb push_back
#define form(m,it) for(auto it=m.begin(); it!=m.end(); it++)
#define forp(i,a,b) for(ll i=a; i<=b; i++)
#define forn(i,a,b) for(ll i=a; i>=b; i--)
#define newl '\n'
ll cnt[3][3][100005];
ll seq[2][3][100005];

void init(string a, string b){
    ll n=a.length();

    forp(i,0,n-1){
        a[i]=(a[i]=='T')?'B':a[i];
        b[i]=(b[i]=='T')?'B':b[i];
    }

    forp(i,1,n){
        forp(i1,0,2){
            forp(i2,0,2){
                if(a[i-1]==(char)(i1+'A')&&b[i-1]==(char)(i2+'A')){
                    cnt[i1][i2][i]=cnt[i1][i2][i-1]+1;
                } else {
                    cnt[i1][i2][i]=cnt[i1][i2][i-1];
                }
                //cout<<(char)(i1+'A')<<" "<<(char)(i2+'A')<<" "<<i<<" "<<cnt[i1][i2][i]<<newl;
            }
        }
        forp(j,0,2){
            if(a[i-1]==(char)(j+'A')){
                seq[0][j][i]=seq[0][j][i-1]+1;
            } else {
                seq[0][j][i]=seq[0][j][i-1];
            }
            if(b[i-1]==(char)(j+'A')){
                seq[1][j][i]=seq[1][j][i-1]+1;
            } else {
                seq[1][j][i]=seq[1][j][i-1];
            }
        }
    }
}

int get_distance(int x, int y){
    x++; y++;
    forp(j,0,2){
        if(seq[0][j][y]-seq[0][j][x-1]!=seq[1][j][y]-seq[1][j][x-1]){
            return -1;
        }
    }

    ll c=0;
    ll ans=0;
    forp(i,0,2){
        forp(j,i+1,2){
            ans+=min((cnt[j][i][y]-cnt[j][i][x-1]),(cnt[i][j][y]-cnt[i][j][x-1]));
            c+=2*min((cnt[j][i][y]-cnt[j][i][x-1]),(cnt[i][j][y]-cnt[i][j][x-1]));
        }
        c+=(cnt[i][i][y]-cnt[i][i][x-1]);
    }

    ans+=2*((y-x+1-c)/3);
    return ans;
}

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