Submission #564307

#	Time	Username	Problem	Language	Result	Execution time	Memory
564307		2fat2code	Mutating DNA (IOI21_dna)	C++17	100 / 100	45 ms	7368 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
//#define int long long
using namespace std;

const int nmax = 100005;

int n, pref[3][3][nmax];

void init(string a, string b) {
    n = (int)a.size();
    for(int i=0;i<n;i++){
        if(a[i] == 'A') a[i] = '0';
        else if(a[i] == 'C') a[i] = '1';
        else a[i] = '2';
        if(b[i] == 'A') b[i] = '0';
        else if(b[i] == 'C') b[i] = '1';
        else b[i] = '2';
    }
    for(int i=0;i<n;i++){
        pref[a[i]-'0'][b[i]-'0'][i+1]++;
        for(int j=0;j<=2;j++){
            for(int t=0;t<=2;t++){
                pref[j][t][i+1] += pref[j][t][i];
            }
        }
    }
}

int get_distance(int x, int y) {
	int dp[3][3];
	for(int i=0;i<=2;i++){
        for(int j=0;j<=2;j++){
            dp[i][j] = (pref[i][j][y+1] - pref[i][j][x]);
        }
	}
	int ans = 0;
	for(int i=0;i<=2;i++){
        int cnt1 = dp[i][0] + dp[i][1] + dp[i][2];
        int cnt2 = dp[0][i] + dp[1][i] + dp[2][i];
        if(cnt1 != cnt2) return -1;
	}
	for(int i=0;i<=2;i++){
        for(int j=i+1;j<=2;j++){
            int curr = min(dp[i][j], dp[j][i]);
            ans += curr;
            dp[i][j] -= curr;
            dp[j][i] -= curr;
        }
	}
	int cnt = 0;
	for(int i=0;i<=2;i++){
        for(int j=i+1;j<=2;j++){
            if(dp[i][j] != 0) cnt = dp[i][j];
        }
	}
	ans += 2*cnt;
	return ans;
}

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