Submission #758351

#	Time	Username	Problem	Language	Result	Execution time	Memory
758351		raysh07	Mutating DNA (IOI21_dna)	C++17	100 / 100	49 ms	8468 KiB

dna

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

const int N = 5e5 + 69;
int a[N][3];
int b[N][3];
int p[N][3][3];
int n;

void init(string A, string B) {
    n = A.length();
    for (int i = 1; i <= n; i++){
        if (A[i - 1] == 'A') a[i][0]++;
        else if (A[i - 1] == 'T') a[i][1]++;
        else a[i][2]++;
    }
    
    for (int i = 1; i <= n; i++){
        if (B[i - 1] == 'A') b[i][0]++;
        else if (B[i - 1] == 'T') b[i][1]++;
        else b[i][2]++;
    }
    
    for (int i = 1; i <= n; i++){
        int k1 = 0, k2 = 0;
        for (int j = 0; j < 3; j++){
            if (a[i][j] > 0) k1 = j;
            if (b[i][j] > 0) k2 = j;
        }
        
        p[i][k1][k2]++;
    }
    
    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++)
            p[i][j][k] += p[i - 1][j][k];
        }
    }
}

int get_distance(int x, int y) {
    x++; 
    y++;
    
    int ans = 0;
    for (int j = 0; j < 3; j++){
        int v1 = a[y][j] - a[x - 1][j];
        int v2 = b[y][j] - b[x - 1][j];
        
        if (v1 != v2) return -1;
    }
    
    int change[3][3];
    for (int j = 0; j < 3; j++){
        for (int k = 0; k < 3; k++){
            if (j != k)
            change[j][k] = p[y][j][k] - p[x - 1][j][k];
            else change[j][k] = 0;
        }
    }
    
    for (int j = 0; j < 3; j++){
        for (int k = j + 1; k < 3; k++){
            int op = min(change[j][k], change[k][j]);
            
            ans += op;
            change[j][k] -= op;
            change[k][j] -= op;
            
            ans += change[j][k] + change[k][j];
        }
    }
    
    int mx = -1;
    
    for (int j = 0; j < 3; j++){
        for (int k = 0; k < 3; k++){
            mx = max(mx, change[j][k]);
        }
    }
    
    ans -= mx;
	return ans;
}

// int32_t main(){
//     string a, b; cin >> a >> b;
//     init(a, b);
    
//     int q; cin >> q;
//     while(q--){
//         int x, y; cin >> x >> y;
//         cout << get_distance(x, y) << "\n";
//     }
//     return 0;
// }

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