Submission #768749

#	Time	Username	Problem	Language	Result	Execution time	Memory
768749		ZeroCool	Mutating DNA (IOI21_dna)	C++17	100 / 100	50 ms	11220 KiB

dna

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



using namespace std;

const int inf = 1e18;

struct Fenwick{
	vector<int> bit;

	Fenwick(int n){
		bit.resize(2 * n + 2,0);
	}

	void update(int i){
		for(i++;i < (int)(bit.size());i += i & -i)bit[i]++;
	}

	int get(int i){
		int ans = 0;
		for(i++;i;i -= i & -i)ans += bit[i];
		return ans;
	}
	int query(int x,int y){
		return get(y) - get(x-1);
	}
};

vector<Fenwick> fwt;

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

void init(string A, string B) {
	int n = A.length();
	fwt.resize(9,Fenwick(n));

	for(int i = 0;i<n;i++){
		int a = get(A[i]);
		int b = get(B[i]);

		fwt[a * 3 + b].update(i);
	}
}

int32_t get_distance(int x, int y) {
	int at = fwt[1].query(x,y);
	int ac = fwt[2].query(x,y);
	int tc = fwt[5].query(x,y);
	int ta = fwt[3].query(x,y);
	int ca = fwt[6].query(x,y);
	int ct = fwt[7].query(x,y);
	int ans = 0;
	int tmp = min(at,ta);
	ans += tmp;
	at -= tmp;
	ta -= tmp;
	tmp = min(ac,ca);
	ans += tmp;
	ac -= tmp;
	ca -= tmp;
	tmp = min(tc,ct);
	ans+=tmp;
	tc-=tmp;
	ct-=tmp;
	if(ac + at + tc + ta + ca + ct == 0)return ans;
	if(!((ac && ct && ta) || (at && tc && ca)))return -1;
	if(ac){
		if(ac != ct || ac != ta)return -1;
		ans += ac*2;
	}else{
		if(ca != tc || ca != at)return -1;
		ans += ca*2;
	}
	return ans;
}

Compilation message (stderr)

dna.cpp:8:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    8 | const int inf = 1e18;
      |                 ^~~~

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