Submission #560376

#	Time	Username	Problem	Language	Result	Execution time	Memory
560376		sentheta	Mutating DNA (IOI21_dna)	C++17	100 / 100	40 ms	8572 KiB

dna

#include "dna.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second

#define rand() (uniform_int_distribution<int>(0,1<<30)(rng))
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define dbg(x) cout<<"?"<< #x <<" : "<<(x)<<endl; cout.flush();
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define all(x) (x).begin(), (x).end()

const int N = 1e5+5;

int n;
int cnt[3][N];
int p[3][3][N];

int f(char c){
	if(c=='A') return 0;
	if(c=='C') return 1;
	if(c=='T') return 2;
	return -1;
}

int qry(int l,int r,int* arr){
	int ret = arr[r];
	if(l) ret -= arr[l-1];
	return ret;
}

void init(string s,string t){
	n = s.size();

	rep(i,0,n){
		int x = f(s[i]), y = f(t[i]);

		if(i){
			rep(j,0,3) cnt[j][i] = cnt[j][i-1];
			rep(j,0,3) rep(k,0,3)
				p[j][k][i] = p[j][k][i-1];
		}
		else{
			rep(j,0,3) cnt[j][i] = 0;
			rep(j,0,3) rep(k,0,3)
				p[j][k][i] = 0;
		}
		cnt[x][i]++;
		cnt[y][i]--;
		p[x][y][i]++;
	}
}

int get_distance(int x,int y){
	rep(i,0,3) if(qry(x,y,cnt[i]) != 0){
		return -1;
	}

	int ans = 0;

	int a[3][3];
	rep(i,0,3) rep(j,0,3){
		if(i!=j) a[i][j] = qry(x,y,p[i][j]);
		else a[i][j] = 0;
	}

	// ij <--> ji
	rep(i,0,3) rep(j,0,i){
		int mov = min(a[i][j], a[j][i]);
		ans += mov;
		a[i][j] -= mov;
		a[j][i] -= mov;
	}

	int rem = 0;
	rep(i,0,3) rep(j,0,3){
		rem += a[i][j];
	}
	ans += rem/3*2;

	return ans;
}

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