Submission #438823

#	Time	Username	Problem	Language	Result	Execution time	Memory
438823		snokes	Mutating DNA (IOI21_dna)	C++17	56 / 100	55 ms	5308 KiB

dna

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

const int mxN = 1e5 + 123;
int pref[mxN];
int cntA[mxN][3], cntB[mxN][3], N;
map<char, int> m = {{'A', 0}, {'C', 1}, {'T', 2}};

void init(string a, string b)
{
    for(int i = 0; i < mxN;i++)
    {
        for(int j = 0; j < 3;j++)
        {
            cntA[i][j] = cntB[i][j] = 0;
        }
        pref[i] = 0;
    }
    //Say a is the 'original'
    assert(a.size() == b.size());
    N = a.size();
    for(int i = 0; i < N;i++)
    {
        for(int j = 0; j < 3;j++)
        {
            cntA[i+1][j] = cntA[i][j];
            cntB[i+1][j] = cntB[i][j];
        }
        ++cntA[i+1][m[a[i]]];
        ++cntB[i+1][m[b[i]]];
        pref[i+1] = pref[i] + (a[i] != b[i]);
    }
}

int get_distance(int L, int R)
{
    ++R;
    bool ok = 1;
    for(int i = 0; i < 3;i++)
        if(cntA[R][i] - cntA[L][i] != cntB[R][i] - cntB[L][i])
            ok = 0;
    if(!ok) return -1;
    int bad = pref[R] - pref[L];
    return (bad + 1) / 2;
}
/*
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s, t;
    cin >> s >> t;
    init(s, t);
    int Q;
    cin >> Q;
    while(Q--)
    {
        int a, b;
        cin >> a >> b;
        cout << get_distance(a, b) << "\n";
    }
}
*/

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