Submission #538238

#	Time	Username	Problem	Language	Result	Execution time	Memory
538238		MrTEK	Mutating DNA (IOI21_dna)	C++17	100 / 100	132 ms	12296 KiB

dna

#include "dna.h"
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <climits>
#include <ctime>
 
 
using namespace std;
 
const int N = 1e5 + 5;

char s1[N],s2[N];
int n;


int f(int x,int y) {
	if (s1[x] == 'A' && s2[y] == 'T')
		return 0;
	if (s1[x] == 'T' && s2[y] == 'A')
		return 1;
	if (s1[x] == 'A' && s2[y] == 'C')
		return 2;
	if (s1[x] == 'C' && s2[y] == 'A')
		return 3;
	if (s1[x] == 'C' && s2[y] == 'T')
		return 4;
	if (s1[x] == 'T' && s2[y] == 'C')
		return 5;
	return 6;
}

struct node {
	int cnt[7];
	int swp;

    node operator+(node oth) {
    	node res;

    	res.swp = swp + oth.swp;

    	for (int i = 0 ; i < 7 ; i++)
    		res.cnt[i] = cnt[i] + oth.cnt[i];

    	int simplify01 = min(res.cnt[0],res.cnt[1]);
    	int simplify23 = min(res.cnt[2],res.cnt[3]);
    	int simplify45 = min(res.cnt[4],res.cnt[5]);

    	res.swp += simplify01 + simplify23 + simplify45;

    	res.cnt[0] -= simplify01;
    	res.cnt[1] -= simplify01;
    	res.cnt[2] -= simplify23;
    	res.cnt[3] -= simplify23;
    	res.cnt[4] -= simplify45;
    	res.cnt[5] -= simplify45;

    	return res;
    }

}tree[N<<2],zero;


void init_tree(int ind,int l,int r) {

	if (l == r) {
		tree[ind].cnt[f(l,r)] = 1;
		return;
	}

	int mid = (l + r) / 2;

	init_tree(ind + ind,l,mid);
	init_tree(ind + ind + 1,mid + 1,r);

	tree[ind] = tree[ind + ind] + tree[ind + ind + 1];

}

void init(std::string a, std::string b) {
	n = a.size();
	for (int i = 0 ; i < a.size() ; i++)
		s1[i + 1] = a[i];

	for (int i = 0 ; i < b.size() ; i++)
		s2[i + 1] = b[i];

	init_tree(1,1,n);
	// cout << "init : " << tree[1].swp << endl;
}

node query(int ind,int l,int r,int lw,int rw) {
	if (l > rw || r < lw)
		return zero;

	if (l >= lw && r <= rw)
		return tree[ind];

	int mid = (l + r) / 2;
	return query(ind + ind,l,mid,lw,rw) + query(ind + ind + 1,mid + 1,r,lw,rw);
}

int get_distance(int x, int y) {

	x++;
	y++;
	node res = query(1,1,n,x,y);

	// cerr << "new:\n------\n";

	// for (int i = 0 ; i < 6 ; i++)
	// 	cout << i << " -> " << res.cnt[i] << endl;


	// cout << "swap : " << res.swp << endl;


	int ans1 = -1;
	if (res.cnt[1] || res.cnt[4] || res.cnt[2])
		ans1 = -1;
	else if (res.cnt[0] == res.cnt[5] && res.cnt[5] == res.cnt[3])
		ans1 = res.cnt[0] * 2 + res.swp;
	else ans1 = -1;

	
	int ans2 = -1;
	if (res.cnt[0] || res.cnt[5] || res.cnt[3])
		ans2 = -1;		
	else if (res.cnt[1] == res.cnt[4] && res.cnt[4] == res.cnt[2])
		ans2 = res.cnt[1] * 2 + res.swp;
	else ans2 = -1;


	// cerr << ans1 << " " << ans2 << endl;

	return max(ans1,ans2);
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for (int i = 0 ; i < a.size() ; i++)
      |                   ~~^~~~~~~~~~
dna.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for (int i = 0 ; i < b.size() ; i++)
      |                   ~~^~~~~~~~~~

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