제출 #829229

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

dna

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

int n, cnt[maxn][6], part[maxn][9];

void init(std::string s, std::string t) {
	n = s.size();
	for (int i = 1; i <= n; i++){
		int x = (s[i-1] == 'A'? 0: (s[i-1] == 'T'? 1: 2));
		int y = (t[i-1] == 'A'? 0: (t[i-1] == 'T'? 1: 2));
		cnt[i][x]++;
		cnt[i][y+3]++;
		part[i][x*3+y]++;
	}
	for (int j = 0; j < 9; j++){
		for (int i = 1; i <= n; i++){
			part[i][j] += part[i-1][j];
			if (j < 6) cnt[i][j] += cnt[i-1][j];
		}
	}
}


int get_distance(int x, int y) {
	y++, x++;
	for (int i = 0; i < 3; i++){
		if (cnt[y][i] - cnt[x-1][i] != cnt[y][i+3] - cnt[x-1][i+3]) return -1;
	}
	int tmp[9];
	for (int i = 0; i < 9; i++){
		tmp[i] = part[y][i] - part[x-1][i];
	//	debug(i, tmp[i]);
	}
	int res = 0;
	for (int i = 0; i < 9; i++){
		int x = i / 3, y = i % 3;
		int idx = y * 3 + x;
		int val = min(tmp[i], tmp[idx]);
		//debug(i, idx, val);
		res += val;
		tmp[i] -= val;
		if (idx != i) tmp[idx] -= val;
	}
	assert(tmp[1] == tmp[5] && tmp[5] == tmp[6] && tmp[2] == tmp[7] && tmp[7] == tmp[3]);
	res += tmp[1] + tmp[2];
	return y - x + 1 - res;
}

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