Submission #792006

#	Time	Username	Problem	Language	Result	Execution time	Memory
792006		Karpin	Mutating DNA (IOI21_dna)	C++17	100 / 100	49 ms	8780 KiB

dna

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

using namespace std;

#define ll long long
#define vt vector


vt<int> aamountofA;
vt<int> aamountofT;
vt<int> aamountofC;

vt<int> bamountofA;
vt<int> bamountofT;
vt<int> bamountofC;

vt<int>amountofAT;
vt<int>amountofAC;
vt<int>amountofTA;
vt<int>amountofTC;
vt<int>amountofCA;
vt<int>amountofCT;


void init(std::string a, std::string b) {

	for(int i = 0; i < a.length(); i++){
		aamountofA.push_back(0);
		aamountofT.push_back(0);
		aamountofC.push_back(0);

		bamountofA.push_back(0);
		bamountofT.push_back(0);
		bamountofC.push_back(0);

		amountofAT.push_back(0);
		amountofAC.push_back(0);
		amountofTA.push_back(0);
		amountofTC.push_back(0);
		amountofCA.push_back(0);
		amountofCT.push_back(0);
	}

	if (a[0] == 'A') aamountofA[0] = 1;
	if (a[0] == 'T') aamountofT[0] = 1;
	if (a[0] == 'C') aamountofC[0] = 1;

	if (b[0] == 'A') bamountofA[0] = 1;
	if (b[0] == 'T') bamountofT[0] = 1;
	if (b[0] == 'C') bamountofC[0] = 1;


	if (a[0] == 'A' && b[0] == 'T') amountofAT[0] = 1;
	if (a[0] == 'A' && b[0] == 'C') amountofAC[0] = 1;
	if (a[0] == 'T' && b[0] == 'A') amountofTA[0] = 1;
	if (a[0] == 'T' && b[0] == 'C') amountofTC[0] = 1;
	if (a[0] == 'C' && b[0] == 'A') amountofCA[0] = 1;
	if (a[0] == 'C' && b[0] == 'T') amountofCT[0] = 1;


	for(int i = 1; i < a.length(); i++){

		aamountofA[i] = aamountofA[i - 1];
		aamountofC[i] = aamountofC[i - 1];
		aamountofT[i] = aamountofT[i - 1];

		bamountofA[i] = bamountofA[i - 1];
		bamountofC[i] = bamountofC[i - 1];
		bamountofT[i] = bamountofT[i - 1];

		amountofAT[i] = amountofAT[i - 1];
		amountofAC[i] = amountofAC[i - 1];
		amountofTA[i] = amountofTA[i - 1];
		amountofTC[i] = amountofTC[i - 1];
		amountofCA[i] = amountofCA[i - 1];
		amountofCT[i] = amountofCT[i - 1];


		if(a[i] == 'A') aamountofA[i] = aamountofA[i - 1] + 1;
		if(a[i] == 'T') aamountofT[i] = aamountofT[i - 1] + 1;
		if(a[i] == 'C') aamountofC[i] = aamountofC[i - 1] + 1;

		if(b[i] == 'A') bamountofA[i] = bamountofA[i - 1] + 1;
		if(b[i] == 'T') bamountofT[i] = bamountofT[i - 1] + 1;
		if(b[i] == 'C') bamountofC[i] = bamountofC[i - 1] + 1;

		if (a[i] == 'A' && b[i] == 'T') amountofAT[i] = amountofAT[i - 1] + 1;
		if (a[i] == 'A' && b[i] == 'C') amountofAC[i] = amountofAC[i - 1] + 1;
		if (a[i] == 'T' && b[i] == 'A') amountofTA[i] = amountofTA[i - 1] + 1;
		if (a[i] == 'T' && b[i] == 'C') amountofTC[i] = amountofTC[i - 1] + 1;
		if (a[i] == 'C' && b[i] == 'A') amountofCA[i] = amountofCA[i - 1] + 1;
		if (a[i] == 'C' && b[i] == 'T') amountofCT[i] = amountofCT[i - 1] + 1;
	}
}

int get_distance(int x, int y) {
	int firstamountofA = aamountofA[y];
	int firstamountofC = aamountofC[y];
	int firstamountofT = aamountofT[y];

	int secamountofA = bamountofA[y];
	int secamountofC = bamountofC[y];
	int secamountofT = bamountofT[y];

	int amofAT = amountofAT[y];
	int amofAC = amountofAC[y];
	int amofTA = amountofTA[y];
	int amofTC = amountofTC[y];
	int amofCA = amountofCA[y];
	int amofCT = amountofCT[y];

	if(x > 0){
		firstamountofA -= aamountofA[x - 1];
		firstamountofC -= aamountofC[x - 1];
		firstamountofT -= aamountofT[x - 1];

		secamountofC -= bamountofC[x - 1];
		secamountofT -= bamountofT[x - 1];
		secamountofA -= bamountofA[x - 1];

		amofAT -= amountofAT[x - 1];
		amofAC -= amountofAC[x - 1];
		amofTA -= amountofTA[x - 1];
		amofTC -= amountofTC[x - 1];
		amofCA -= amountofCA[x - 1];
		amofCT -= amountofCT[x - 1];
	}


	if (firstamountofA != secamountofA) return -1;
	if (firstamountofT != secamountofT) return -1;
	if (firstamountofC != secamountofC) return -1;

	ll res = 0;


	res += min(amofAT, amofTA);
	res += min(amofAC, amofCA);
	res += min(amofTC, amofCT);

	int realamofAT = max(0, amofAT - amofTA);
	int realamofTA = max(0, amofTA - amofAT);
	int realamofAC = max(0, amofAC - amofCA);
	int realamofCA = max(0, amofCA - amofAC);
	int realamofTC = max(0, amofTC - amofCT);
	int realamofCT = max(0, amofCT - amofTC);

	res += 2 * (realamofAC + realamofCA);

	return res;

}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i = 0; i < a.length(); i++){
      |                 ~~^~~~~~~~~~~~
dna.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i = 1; i < a.length(); i++){
      |                 ~~^~~~~~~~~~~~
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:142:6: warning: unused variable 'realamofAT' [-Wunused-variable]
  142 |  int realamofAT = max(0, amofAT - amofTA);
      |      ^~~~~~~~~~
dna.cpp:143:6: warning: unused variable 'realamofTA' [-Wunused-variable]
  143 |  int realamofTA = max(0, amofTA - amofAT);
      |      ^~~~~~~~~~
dna.cpp:146:6: warning: unused variable 'realamofTC' [-Wunused-variable]
  146 |  int realamofTC = max(0, amofTC - amofCT);
      |      ^~~~~~~~~~
dna.cpp:147:6: warning: unused variable 'realamofCT' [-Wunused-variable]
  147 |  int realamofCT = max(0, amofCT - amofTC);
      |      ^~~~~~~~~~

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