Submission #483706

#	Time	Username	Problem	Language	Result	Execution time	Memory
483706		tredsused70	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	8212 KiB

dna

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
using namespace std;
 
#define accelerator ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int nmax=200011,mod=1000000007,inf=2000010000,key=200003;
const ll infll=4000000000000000000;
const ld eps=1e-7;
 
string a,b;
int cntc[nmax][3]={0},mas1[nmax]={0},mas2[nmax]={0},cnt[nmax][3][3]={0};

void cnv(string s,int mas[])
{
    int n=s.size();
    for(int i=0;i<n;i++)
    {
        if(s[i]=='A')
        {
            mas[i+1]=0;
            continue;
        }
        if(s[i]=='T')
            mas[i+1]=1;
        else
            mas[i+1]=2;
    }
    return ;
}
 
void init(string a,string b)
{
    cnv(a,mas1);
    cnv(b,mas2);
    int n=a.size();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<3;j++)
            cntc[i+1][j]=cntc[i][j];
        cntc[i+1][mas1[i+1]]++;
        cntc[i+1][mas2[i+1]]--;
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                cnt[i+1][j][k]=cnt[i][j][k];
        cnt[i+1][mas1[i+1]][mas2[i+1]]++;
    }
    return ;
}
 
int count_swaps(int mas[3][3])
{
    int ans=0,t;
    for(int i=0;i<3;i++)
    {
        mas[i][i]=0;
        for(int j=i+1;j<3;j++)
        {
            t=min(mas[i][j],mas[j][i]);
            ans+=t;
            mas[i][j]-=t;
            mas[j][i]-=t;
        }
    }
    t=0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            t+=mas[i][j];
    ans+=2*t/3;
    return ans;
}
 
int get_distance(int l,int r)
{
    r++;
    for(int i=0;i<3;i++)
    {
        if(cntc[l][i]!=cntc[r][i])
            return -1;
    }
    int cntt[3][3];
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        {
            cntt[i][j]=cnt[r][i][j];
            cntt[i][j]-=cnt[l][i][j];
        }
    return count_swaps(cntt);
}

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