Submission #1293745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293745		AbdullahIshfaq	Mutating DNA (IOI21_dna)	C++20	100 / 100	23 ms	6124 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define MOD 998244353
int dp[100100][3][3];
void init(string a, string b)
{
    string key = "ACT";
    for (int i = 1; i <= a.size(); i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                dp[i][j][k] = dp[i - 1][j][k] + (a[i - 1] == key[j] and b[i - 1] == key[k]);
}

int get_distance(int l, int r)
{
    int ans = 0, prev = 0;
    for (int i = 0; i < 3; i++)
    {
        int next = (i + 1) % 3, x = dp[r + 1][i][next] - dp[l][i][next], y = dp[r + 1][next][i] - dp[l][next][i];
        if (i)
        {
            if (prev + y != x){
                return -1;
            }
        }
        else{
            prev = x - y;
            ans += 2 * abs(prev);
        }
        ans += min(x, y);
    }
    return ans;
}

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