Submission #815924

#	Time	Username	Problem	Language	Result	Execution time	Memory
815924		blackyuki	Mutating DNA (IOI21_dna)	C++17	100 / 100	43 ms	10584 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001001001;
vvvi rui;
void init(std::string a, std::string b) {
	ll n=a.size();
	rui=vvvi(3,vvi(2,vi(n+1)));
	rep(i,n)if(a[i]!=b[i]){
		if(a[i]=='A'&&b[i]=='C')rui[0][0][i+1]++;
		if(a[i]=='C'&&b[i]=='A')rui[0][1][i+1]++;
		if(a[i]=='C'&&b[i]=='T')rui[1][0][i+1]++;
		if(a[i]=='T'&&b[i]=='C')rui[1][1][i+1]++;
		if(a[i]=='T'&&b[i]=='A')rui[2][0][i+1]++;
		if(a[i]=='A'&&b[i]=='T')rui[2][1][i+1]++;
	}
	rep(i,3)rep(j,2)rep(k,n)rui[i][j][k+1]+=rui[i][j][k];
}

int get_distance(int x, int y) {
	vvi v(3,vi(2));
	rep(i,3)rep(j,2)v[i][j]=rui[i][j][y+1]-rui[i][j][x];
	ll ans=0;
	rep(i,3){
		ll t=min(v[i][0],v[i][1]);
		ans+=t;
		v[i][0]-=t;
		v[i][1]-=t;
	}
	rep(i,2){
		if(v[0][i]!=v[1][i]||v[1][i]!=v[2][i])return -1;
		ans+=v[0][i]*2;
	}
	return ans;
}

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