Submission #781425

#	Time	Username	Problem	Language	Result	Execution time	Memory
781425		mindiyak	Mutating DNA (IOI21_dna)	C++17	0 / 100	28 ms	13988 KiB

dna

#include "dna.h"
#include <vector>
#include <algorithm>
// #include <iostream>
#include <set>
#define pb push_back

using namespace std;

char possible[] = {'A','C','T'};
vector<vector<int>> a_counter;
vector<vector<int>> b_counter;
vector<int> a_possible_counter;
vector<int> b_possible_counter;
vector<vector<int>> a_pos;
string A,B;

void init(string a, string b) {
	A = a;
	B = b;
	vector<int> arr;
	set<int> arr1;
	for(int i=0;i<3;i++){
		a_counter.pb(arr);
		b_counter.pb(arr);
		a_pos.pb(arr);
	}

	a_counter[0].pb(0);
	a_counter[1].pb(0);
	a_counter[2].pb(0);

	b_counter[0].pb(0);
	b_counter[1].pb(0);
	b_counter[2].pb(0);

	int ka = 0,kc = 0,kt = 0;
	for(int i=0;i<a.size();i++){
		if(a[i] == 'A'){
			ka++;
		}
		else if(a[i] == 'C'){
			kc++;
		}
		else{
			kt++;
		}
		a_counter[0].pb(ka);
		a_counter[1].pb(kc);
		a_counter[2].pb(kt);

		for(int j=0;j<3;j++){
			if(a[i] == possible[j]){
				a_pos[j].pb(i);
				a_possible_counter.pb(j);
			}
		}
	}


	// for(int i=0;i<a.size();i++){
	// 	cout << a_possible_counter[i] << " ";
	// }cout << endl;

	// cout << "A processed "<< endl;

	ka = 0,kc = 0,kt = 0;
	for(int i=0;i<b.size();i++){
		if(b[i] == 'A'){
			ka++;
		}
		else if(b[i] == 'C'){
			kc++;
		}
		else{
			kt++;
		}

		b_counter[0].pb(ka);
		b_counter[1].pb(kc);
		b_counter[2].pb(kt);

		for(int j=0;j<3;j++){
			if(b[i] == possible[j]){
				b_possible_counter.pb(j);
			}
		}
	}
	// cout << "B processed "<< endl;
}

int get_distance(int x, int y) {
	for(int i=0;i<3;i++){
		// cout << possible[i] << " " << (a_counter[i][y+1]-a_counter[i][x]) << " " << (b_counter[i][y+1]-b_counter[i][x]) << endl;
		if((a_counter[i][y+1]-a_counter[i][x]) != (b_counter[i][y+1]-b_counter[i][x])){
			return -1;
		}
	}

	int ans = 0;
	vector<bool> solved((y-x),false);
	set<int> a_used;
	set<int> c_used;
	set<int> t_used;
	int starter[] = {0,0,0};

	for(int i=0;i<(y-x);i++){
		if(solved[i])
			continue;
		// cout << x << " " << y << endl;
		// cout << "Two chars " << possible[a_possible_counter[x+i]] << " " << possible[b_possible_counter[x+i]] << endl;
		if(a_possible_counter[x+i] == b_possible_counter[x+i])
			continue;
		int next_char = b_possible_counter[x+i];
		// cout << "next_char " << next_char << " " << a_pos[next_char].size() << endl;

		int it1 = lower_bound(a_pos[next_char].begin()+starter[next_char],a_pos[next_char].end(),x)-a_pos[next_char].begin();
		int it2 = upper_bound(a_pos[next_char].begin()+starter[next_char],a_pos[next_char].end(),y)-a_pos[next_char].begin();

		// cout << it1 << " " << it2 << endl;

		if(it1 < it2){
			solved[a_pos[next_char][it1]] = true;
			starter[next_char]++;
		}

		// cout << "arr ";
		// for(auto j=from;j<to;j++){
		// 	cout << *j << " ";
		// }cout << endl;
		// cout << "y " << y << endl;

		// cout << "find " << it-from  << " " << to-from << endl;
		// if(it == to){
		// 	solved[(it - from)+i] = true;
		// }
		ans ++ ;
		// cout << endl;
	}


	return ans;
}

Compilation message (stderr)

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

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