Submission #1086655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086655		Icelast	Mutating DNA (IOI21_dna)	C++17	100 / 100	36 ms	7524 KiB

dna

#include "dna.h"
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
int pf[maxn][3][3];
void init(std::string a, std::string b) {
    int n = a.size();
    a = ' ' + a;
    b = ' ' + b;
    map<char, int> mp;
    mp['A'] = 0;
    mp['T'] = 1;
    mp['C'] = 2;
    for(int i = 1; i <= n; i++){
        for(int p = 0; p < 3; p++){
            for(int q = 0; q < 3; q++){
                pf[i][p][q] = pf[i-1][p][q];
            }
        }
        int p = mp[a[i]], q = mp[b[i]];
        pf[i][p][q]++;
    }
}

int get_distance(int x, int y) {
    x++; y++;
    vector<vector<int>> d(3, vector<int>(3, 0));
    vector<int> cnt(3, 0);
    for(int p = 0; p < 3; p++){
        for(int q = 0; q < 3; q++){
            d[p][q] = pf[y][p][q] - pf[x-1][p][q];
            cnt[p] += d[p][q];
            cnt[q] -= d[p][q];
        }
    }
    for(int i = 0; i < 3; i++){
        if(cnt[i] != 0) return -1;
    }
    int ans = 0, lt = 0;
    for(int p = 0; p < 3; p++){
        for(int q = 0; q < p; q++){
            int diff = min(d[p][q], d[q][p]);
            d[p][q] -= diff;
            d[q][p] -= diff;
            ans += diff;
            lt = max(d[p][q], d[q][p]);
        }
    }
    ans += lt*2;
    return ans;
}

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