Submission #995574

#	Time	Username	Problem	Language	Result	Execution time	Memory
995574		mindiyak	Mutating DNA (IOI21_dna)	C++17	100 / 100	76 ms	27936 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, int> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ld> vd;
typedef vector<long> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;

vvi A(100010, vi(3,0));
vvi B(100010, vi(3,0));
vvi types(100010, vi(23,0));

int to_int(char a){
	if(a == 'A')return 0;
	if(a == 'C')return 1;
	return 2;
}

int to_pair(char a,char b){
	return to_int(a)*10+to_int(b);
}

void init(std::string a, std::string b) {
	FOR(i,1,a.size()+1){
		FOR(j,0,3)A[i][j] = A[i-1][j];
		FOR(j,0,3)B[i][j] = B[i-1][j];
		FOR(j,0,23)types[i][j] = types[i-1][j];
		A[i][to_int(a[i-1])] += 1;
		B[i][to_int(b[i-1])] += 1;
		types[i][to_pair(a[i-1],b[i-1])] += 1;
	}

	// FOR(i,0,a.size()+1){
	// 	FOR(j,0,3){
	// 		cout << A[i][j] << " ";
	// 	}cout << endl;
	// }cout << endl;

	// FOR(i,0,a.size()+1){
	// 	FOR(j,0,3){
	// 		cout << B[i][j] << " ";
	// 	}cout << endl;
	// }cout << endl;
}

int ans = 0;
int num_errors = 0;

void quick(int x,int y,int a,int b){
	int temp = min(types[y][a] - types[x][a],types[y][b] - types[x][b]);
	num_errors -= temp * 2;
	ans += temp;
}

int get_distance(int x, int y) {
	// cout << "############" << endl;
	y++;
	FOR(i,0,3){
		// cout << i << " "  << A[y][i] << " - " << A[x][i] << " " << B[y][i]  << " - " <<  B[x][i] << endl;
		if(A[y][i] - A[x][i] != B[y][i] - B[x][i])return -1;
	}

	ans = 0;
	num_errors = 0;

	FOR(j,0,23){
		if(j==0)continue;
		if(j==11)continue;
		if(j==22)continue;
		num_errors += types[y][j] - types[x][j];
	}

	quick(x,y,1,10);
	quick(x,y,2,20);
	quick(x,y,12,21);
	ans += (num_errors/3)*2;

	return ans;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:22:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i, a, b) for (int i = a; i < (b); i++)
      |                                        ^
dna.cpp:56:2: note: in expansion of macro 'FOR'
   56 |  FOR(i,1,a.size()+1){
      |  ^~~

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