Submission #443300

#	Time	Username	Problem	Language	Result	Execution time	Memory
443300		benedict0724	Mutating DNA (IOI21_dna)	C++17	100 / 100	48 ms	9728 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>
using namespace std;

int f(char c)
{
    if(c == 'A') return 0;
    if(c == 'T') return 1;
    if(c == 'C') return 2;
}

int A[100002][3], B[100002][3];
int Ch[100002][3][3];
void init(std::string a, std::string b) {
    int n = a.size();
    for(int i=0;i<n;i++)
    {
        A[i][f(a[i])]++;
        B[i][f(b[i])]++;

        Ch[i][f(a[i])][f(b[i])]++;
    }

    for(int i=1;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            A[i][j]+=A[i-1][j];
            B[i][j]+=B[i-1][j];

            for(int k=0;k<3;k++)
                Ch[i][j][k]+=Ch[i-1][j][k];
        }
    }
}

int get_distance(int x, int y) {
    int ans = 0;
    for(int i=0;i<3;i++)
    {
        if(A[y][i] - (x==0?0:A[x-1][i]) != B[y][i] - (x==0?0:B[x-1][i])) return -1;
    }

    int AT = Ch[y][0][1] - (x==0?0:Ch[x-1][0][1]);
    int AC = Ch[y][0][2] - (x==0?0:Ch[x-1][0][2]);
    int TA = Ch[y][1][0] - (x==0?0:Ch[x-1][1][0]);
    int TC = Ch[y][1][2] - (x==0?0:Ch[x-1][1][2]);
    int CA = Ch[y][2][0] - (x==0?0:Ch[x-1][2][0]);
    int CT = Ch[y][2][1] - (x==0?0:Ch[x-1][2][1]);

    int mAT = min(AT, TA), mAC = min(AC, CA), mTC = min(TC, CT);
    ans += mAT + mAC + mTC;
    ans += (max(AT, TA) - mAT)*2;

	return ans;
}

Compilation message (stderr)

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

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