Submission #955186

#	Time	Username	Problem	Language	Result	Execution time	Memory
955186		IUA_Hasin	Mutating DNA (IOI21_dna)	C++17	56 / 100	37 ms	10840 KiB

dna

#include <bits/stdc++.h>
 
#define endl                                "\n"
#define finp                                for(int i=0; i<n; i++)
#define fknp                                for(int k=0; k<n; k++)
#define yeap                                cout<<"YES"<<endl
#define nope                                cout<<"NO"<<endl
#define inpintn                             int n; cin>>n
#define inpintarrn                          int arr[n]; for(int i=0; i<n; i++){cin>>arr[i];}
#define inpllarrn                           long long arr[n]; for(int i=0; i<n; i++){cin>>arr[i];}
#define ll                                  long long
 
using namespace std;

#include "dna.h"

ll const N = 1e5+10;
string aa, bb;
ll arra[N], arrc[N], arrt[N];
ll brra[N], brrc[N], brrt[N];
ll diff[N], diff2[N];
ll ccnt[N];

void init(std::string a, std::string b) {
	aa = a;
	bb = b;
	ll siz = a.size();
	for(int i=0; i<siz; i++){
		if(a[i]=='A'){
			arra[i+1] = arra[i]+1;
			arrc[i+1] = arrc[i];
			arrt[i+1] = arrt[i];
		} else if(a[i]=='C'){
			arra[i+1] = arra[i];
			arrc[i+1] = arrc[i]+1;
			arrt[i+1] = arrt[i];
		} else {
			arra[i+1] = arra[i];
			arrc[i+1] = arrc[i];
			arrt[i+1] = arrt[i]+1;
		}

		if(b[i]=='A'){
			brra[i+1] = brra[i]+1;
			brrc[i+1] = brrc[i];
			brrt[i+1] = brrt[i];
		} else if(b[i]=='C'){
			brra[i+1] = brra[i];
			brrc[i+1] = brrc[i]+1;
			brrt[i+1] = brrt[i];
		} else {
			brra[i+1] = brra[i];
			brrc[i+1] = brrc[i];
			brrt[i+1] = brrt[i]+1;
		}
	}

	for(int i=0; i<siz; i++){
		char p = aa[i];
		char q = bb[i];
		if(p!=q){
			diff[i+1] = diff[i]+1;
		} else {
			diff[i+1] = diff[i];
		}
	}

	for(int i=0; i<siz; i++){
		char p = aa[i];
		char q = bb[i];
		if(p!=q){
			if(p!='C' && q!='C'){
				diff2[i+1] = diff2[i]+1;
			} else {
				diff2[i+1] = diff2[i];
			}
		} else {
			diff2[i+1] = diff2[i];
		}
	}

	for(int i=0; i<siz; i++){
		char p = aa[i];
		char q = bb[i];
		if(p=='C' && p==q){
			ccnt[i+1] = ccnt[i]+1;
		} else {
			ccnt[i+1] = ccnt[i];
		}
	}

}

int get_distance(int x, int y) {
	x = x+1;
	y = y+1;
	// ll siz1 = aa.size();
	// ll diff[siz1+1];
	// diff[0] = 0;
	// for(int i=0; i<siz1; i++){
	// 	char p = aa[i];
	// 	char q = bb[i];
	// 	if(p!=q){
	// 		diff[i+1] = diff[i]+1;
	// 	} else {
	// 		diff[i+1] = diff[i];
	// 	}
	// }

	ll xa = arra[y]-arra[x-1];
	ll xc = arrc[y]-arrc[x-1];
	ll xt = arrt[y]-arrt[x-1];	
	ll ya = brra[y]-brra[x-1];
	ll yc = brrc[y]-brrc[x-1];
	ll yt = brrt[y]-brrt[x-1];
	ll d = diff[y]-diff[x-1];
	ll d2 = diff2[y]-diff2[x-1];
	ll cc = ccnt[y]-ccnt[x-1];

	// cout << xa << " " << xc << " " << xt << " " << ya << " " << yc << " " << yt << " " << d << " " << d2 << " " << cc << endl;

	if(y-x<=2){
		if(xa==ya && xc==yc && xt==yt){
			if(d==0){
				return 0;
			} else if(d==2){
				return 1;
			} else {
				return 2;
			}
		} else {
			return -1;
		}
	} else {
		if(xa==ya && xc==yc && xt==yt){
			if(xa==0 || xc==0 || xt==0){
				ll ans = d/2;
				return ans; 
			} else {
				if(d2%2==0){
					ll fx = d2/2;
					ll gx = d-fx*2-xc+cc;
					ll ans = fx+gx;
					// cout << fx << " " << gx << " " << ans << endl;
					return ans;
				} else {
					ll fx = floor(d2/2);
					ll gx = d-fx*2-xc+cc;
					ll ans = fx+gx;
					// cout << fx << " " << gx << " " << ans << endl;
					return ans;
				}
			}
		} else {
			return -1;
		}
	}

}

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