Submission #623260

#	Time	Username	Problem	Language	Result	Execution time	Memory
623260		teki	Mutating DNA (IOI21_dna)	C++17	0 / 100	33 ms	6284 KiB

dna

#include <bits/stdc++.h>
#ifndef LOCAL_DEBUG
    #include "dna.h"
#endif

#define pb push_back
#define MS(x,y) memset((x), (y), sizeof((x)))
typedef long long ll;
const ll MN = 1000000007;

using namespace std;

/// A pa T pa C

int pref[2][3][100001];
int prefRaz[100001];
int n;

void init (string a, string b) {
    n = a.length();
    map<char,int> koj;
    koj['A'] = 0;
    koj['T'] = 1;
    koj['C'] = 2;

    MS(pref,0);
    MS(prefRaz,0);

    for (int i = 0; i<n; i++) {
        pref[0][koj[a[i]]][i]++;
        pref[1][koj[b[i]]][i]++;

        if (a[i] != b[i]) prefRaz[i]++;

        if (i != 0) for (int j = 0; j<3; j++) pref[0][j][i] += pref[0][j][i-1];
        if (i != 0) for (int j = 0; j<3; j++) pref[1][j][i] += pref[1][j][i-1];
        if (i != 0) prefRaz[i] += prefRaz[i-1];
    }
}

int get_distance (int posA, int posB) {
    int kol[2][3];
    MS(kol,0);

    for (int i = 0; i<2; i++) {
        for (int j = 0; j<3; j++) {
            kol[i][j] += pref[i][j][posB];

            if (posA != 0) kol[i][j] -= pref[i][j][posA-1];
        }
    }

    for (int i = 0; i<3; i++) if (kol[0][i] != kol[1][i]) return -1;

    int kolRaz = prefRaz[posB];
    if (posA != 0) kolRaz -= prefRaz[posA-1];

    return kolRaz-1;
}

#ifdef LOCAL_DEBUG
int main() {
    #ifdef LOCAL_DEBUG
        fstream cin("in.txt");
    #endif

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    init("ATACAT", "ACTATA");
    cout<<get_distance(1,3)<<endl;
    cout<<get_distance(4,5)<<endl;
}
#endif

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