Submission #558850

#	Time	Username	Problem	Language	Result	Execution time	Memory
558850		anubhavdhar	Mutating DNA (IOI21_dna)	C++17	100 / 100	47 ms	8584 KiB

dna

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

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first 
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double

using namespace std;

#define MAXN 100005

int N;
int pre[3][MAXN];
int trans[3][3][MAXN];

inline int toint(char c){
	return (c == 'A' ? 0 : (c == 'C' ? 1 : 2));
}

void init(string A, string B){
	N = A.size();

	F0R(a, 3){
		F0R(b, 3){
			F0R(i, N){
				trans[a][b][i] = 0;
			}
		}
	}

	F0R(a, 3){
		F0R(i, N){
			pre[a][i] = 0;
		}
	}

	F0R(i, N){
		if(i){
			F0R(a, 3){
				pre[a][i] = pre[a][i - 1];
				F0R(b, 3){
					trans[a][b][i] = trans[a][b][i - 1];
				}
			}
		}
		++pre[toint(A[i])][i];
		--pre[toint(B[i])][i];
		++trans[toint(A[i])][toint(B[i])][i];
	}
}

inline bool ok(int x, int y){
	if(x){
		return pre[0][y] == pre[0][x - 1] && pre[1][y] == pre[1][x - 1] && pre[2][y] == pre[2][x - 1];
	}else{
		return pre[0][y] == 0 && pre[1][y] == 0 && pre[2][y] == 0;
	}
}

int get_distance(int x, int y){
	if(!ok(x, y)){
		return -1;
	}
	int res[3][3];
	F0R(a, 3){
		F0R(b, 3){
			res[a][b] = trans[a][b][y];
			if(x){
				res[a][b] -= trans[a][b][x - 1];
			}
			// cerr << "res[" << a << "][" << b << "] = " << res[a][b] << '\n';
		}
	}

	int cnt[3];
	cnt[0] = min(res[0][1], res[1][0]);
	res[0][1] -= cnt[0];
	res[1][0] -= cnt[0];
	cnt[1] = min(res[2][1], res[1][2]);
	res[2][1] -= cnt[1];
	res[1][2] -= cnt[1];
	cnt[2] = min(res[0][2], res[2][0]);
	res[0][2] -= cnt[2];
	res[2][0] -= cnt[2];
	// F0R(a, 3){
	// 	cerr << "cnt[" << a << "] = " << cnt[a] << '\n';
	// }
	return cnt[0] + cnt[1] + cnt[2] + ((res[0][1] + res[1][0]) << 1);
}
/*
signed main(){


	string A, B;
	int Q;
	cin >> A >> B >> Q;
	init(A, B);
	while(Q--){
		int x, y;
		cin >> x >> y;
		cout << get_distance(x, y) << '\n';
	}
	
	return 0;
}
*/
/*
ACTATA
ATACAT
3
1 3
3 5
4 5
*/

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