Submission #856433

#	Time	Username	Problem	Language	Result	Execution time	Memory
856433		andrei_boaca	Mutating DNA (IOI21_dna)	C++17	100 / 100	36 ms	10264 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
//#include "grader.cpp"



using namespace std;
int s[100005][4][4],cnt[4][4],nr[4];
int n;
int toint(char c)
{
    if(c=='A')
        return 1;
    if(c=='C')
        return 2;
    if(c=='T')
        return 3;
}
void init(std::string a, std::string b) {
    n=a.size();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
                s[i][j][k]=s[i-1][j][k];
        int x=toint(a[i-1]);
        int y=toint(b[i-1]);
        s[i][x][y]++;
    }
}

int get_distance(int x, int y) {
    x++;
    y++;
    nr[1]=nr[2]=0;
    nr[3]=0;
    int ans=0;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
        {
            cnt[i][j]=s[y][i][j]-s[x-1][i][j];
            if(i!=j)
                ans+=cnt[i][j];
            nr[i]+=cnt[i][j];
            nr[j]-=cnt[i][j];
        }
    for(int i=1;i<=3;i++)
        if(nr[i]!=0)
            return -1;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            if(i!=j)
            {
                int val=min(cnt[i][j],cnt[j][i]);
                ans-=val;
                cnt[i][j]-=val;
                cnt[j][i]-=val;
            }
    int t=min(min(cnt[1][2],cnt[2][3]),cnt[3][1]);
    ans-=t;
    cnt[1][2]-=t;
    cnt[2][3]-=t;
    cnt[3][1]-=t;

    t=min(min(cnt[1][3],cnt[2][1]),cnt[3][2]);
    ans-=t;
    cnt[1][3]-=t;
    cnt[2][1]-=t;
    cnt[3][2]-=t;

    return ans;
}

Compilation message (stderr)

dna.cpp: In function 'int toint(char)':
dna.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

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