제출 #466324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
466324		mariowong	DNA 돌연변이 (IOI21_dna)	C++17	100 / 100	61 ms	16384 KiB

dna

//#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int n,ct[5][100005][5],a[5][5],num,num2,tmp,ans;
int ps[100005][5][5];
char s[8]={'A','C','T'};
void init(std::string a, std::string b) {
    n=a.length();
    for (int i=0;i<n;i++){
        for (int j=0;j<3;j++){
            if (a[i] == s[j]) ct[1][i][j]++;
            if (b[i] == s[j]) ct[2][i][j]++;
        }
        for (int j=0;j<3;j++){
        	for (int k=0;k<3;k++){
        		if (a[i] == s[j] && b[i] == s[k])
        		ps[i][j][k]++;
			}
		}
    	if (i == 0) continue;
    	for (int j=0;j<3;j++){
    		for (int k=0;k<3;k++){
    			ps[i][j][k]+=ps[i-1][j][k];
			}
		}
        for (int j=0;j<3;j++){
        	ct[1][i][j]+=ct[1][i-1][j];
        	ct[2][i][j]+=ct[2][i-1][j];
        }
    }
}
 
int get_distance(int x, int y) {
	ans=0;
    for (int i=0;i<3;i++){
        if (x == 0 && ct[1][y][i] != ct[2][y][i])
        return -1;
        if (x != 0 && ct[1][y][i]-ct[1][x-1][i] != ct[2][y][i]-ct[2][x-1][i])
        return -1;
    }
    for (int i=0;i<3;i++){
    	for (int j=0;j<3;j++){
    		if (x == 0) a[i][j]=ps[y][i][j];
    		else a[i][j]=ps[y][i][j]-ps[x-1][i][j];
		}
	}
	for (int i=0;i<3;i++){
		for (int j=0;j<3;j++){
			tmp=min(a[i][j],a[j][i]);
			if (i != j) ans+=tmp;
			a[i][j]-=tmp; 
			if (i != j) a[j][i]-=tmp;
		}
	}
	for (int i=0;i<3;i++){
		for (int j=0;j<3;j++){
			if (a[i][j] != 0)
			return a[i][j]*2+ans;
		}
	}
	return ans;
}
/*
string r,g;
int aa,bb;
int main(){
    cin >> r >> g;
    init(r,g);
    for (int i=1;i<=4;i++){
        cin >> aa >> bb;
        cout << get_distance(aa,bb) << "\n";
    }
}*/

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