Submission #1196260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196260		Amr	Mutating DNA (IOI21_dna)	C++20	100 / 100	25 ms	9804 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define sz size()

const int N  =300005;
string aa , bb;
ll pre[N][3][3];
pair<ll,ll> dd[3][3] = { {{'A','A'}, { 'A','C'}, {'A','T'}},
                {{'C','A'}, { 'C','C'}, {'C','T'}},
                {{'T','A'}, { 'T','C'}, {'T','T'}}
};
ll go(ll x, ll y , ll a, ll b)
{
    a--,b--;
    return pre[y+1][a][b] - pre[x][a][b];
}
ll n;
void init(std::string a, std::string b) {
    aa = 'A', bb = 'B';
    aa += a, bb += b;
    n = a.sz;
    for(int i =1; i <= n; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            for(int k = 0; k < 3; k++)
            {
                pre[i][j][k] = pre[i-1][j][k] + (pair<ll,ll> ({aa[i],bb[i]}) == dd[j][k]);
            }
        }
    }
    //for(int i = 1; i <= n; i++)
    {
   //     for(int j = 0; j < 3; j++) for(int k = 0; k < 3; k++) cout << pre[i][j][k] << " "; cout << endl;
    }
}

int get_distance(int x, int y) {
    ll a12 = go(x,y,1,2), a21 = go(x,y,2,1), a13 = go(x,y,1,3), a31 = go(x,y,3,1), a23 = go(x,y,2,3), a32 = go(x,y,3,2);
    if(a12+a13==a31+a21&&a21+a23==a32+a12&&a13+a23==a32+a31)
    {
        if( max(a12,a21) - min(a12,a21) == max(a13,a31) - min(a13,a31) && max(a12,a21) - min(a12,a21)== max(a23, a32) - min(a23,a32) )
        return  min(a12,a21) + min(a13,a31) +  min(a23,a32) + (max(a12,a21) - min(a12,a21))*2;
    }
	return -1;
}

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