Submission #437965

#	Time	Username	Problem	Language	Result	Execution time	Memory
437965		CyanForces	Mutating DNA (IOI21_dna)	C++17	100 / 100	144 ms	8004 KiB

dna

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#include "dna.h"

map<char, int> charToInt;
vector<vector<vi>> prefCnt;
int n;

void init(std::string a, std::string b) {
	charToInt['A'] = 0;
	charToInt['C'] = 1;
	charToInt['T'] = 2;

	n = sz(a);
	prefCnt.resize(3, vector<vi>(3, vi(n+1)));
	rep(i,0,n) {
		rep(x,0,3) rep(y,0,3) prefCnt[x][y][i+1] = prefCnt[x][y][i];
		prefCnt[charToInt[a[i]]][charToInt[b[i]]][i+1]++;
	}
}

vi operator+(vi a, vi b) {
	vi retvalue(3);
	rep(i,0,3) retvalue[i] = a[i] + b[i];
	return retvalue;
}

void print(vi a) {
	trav(elem, a) cerr << elem << ", ";
	cerr << endl;
}

int get_distance(int x, int y) {
	vector<vi> swapsNeeded(3, vi(3));
	rep(a,0,3) rep(b,0,3) {
		swapsNeeded[a][b] = prefCnt[a][b][y+1] - prefCnt[a][b][x];
	}
	rep(i,0,3) {
		int in = 0;
		int out = 0;
		rep(j,0,3) {
			in += swapsNeeded[j][i];
			out += swapsNeeded[i][j];
		}
		if (in != out) return -1;
	}

	int ans = 0;
	rep(a,0,3) rep(b,a+1,3) {
		int temp = min(swapsNeeded[a][b], swapsNeeded[b][a]);
		ans += temp;
		swapsNeeded[a][b] -= temp;
		swapsNeeded[b][a] -= temp;
	}

	vector<pii> order({pii(0, 1), pii(0, 2), pii(1, 2)});
	//cerr << "ans = " << ans << endl;
	//cerr << "swapsNeeded = " << endl;
	//trav(v, swapsNeeded)
	//	print(v);
	//cerr << endl;

	int bestCost = 1<<30;
	rep(_,0,3) {
		int tempCost = 0;
		vector<vi> currSwapsNeeded = swapsNeeded;
		for(auto [a,b] : order) {
			//cerr << "swapping " << a << ", " << b << endl;
			int temp = min(currSwapsNeeded[a][b], currSwapsNeeded[b][a]);
			tempCost += temp;
			currSwapsNeeded[a][b] -= temp;
			currSwapsNeeded[b][a] -= temp;

			if (currSwapsNeeded[a][b] == 0 && currSwapsNeeded[b][a] == 0) continue;

			if (currSwapsNeeded[a][b] == 0) swap(a, b);
			temp = currSwapsNeeded[a][b];
			int c = 3 - a - b;
			currSwapsNeeded[a][b] = 0;
			currSwapsNeeded[b][c] -= temp;
			currSwapsNeeded[a][c] += temp;
			tempCost += temp;
			//cerr << tempCost << endl;
			//trav(v, currSwapsNeeded)
			//	print(v);
		}
		bestCost = min(bestCost, tempCost);
		next_permutation(all(order));
	}
	return ans + bestCost;
}

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