Submission #639753

#	Time	Username	Problem	Language	Result	Execution time	Memory
639753		ghostwriter	Mutating DNA (IOI21_dna)	C++17	100 / 100	49 ms	7420 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
const int N = 1e5 + 5;
#define getid(x) (x == 'A'? 0 : x == 'T'? 1 : 2)
int n, d[N][3][3], cnt[3][3];
void init(std::string a, std::string b) {
	n = sz(a);
	FOR(i, 0, n - 1) {
		FOR(j, 0, 2)
		FOR(z, 0, 2)
			d[i][j][z] = (i == 0? 0 : d[i - 1][j][z]);
		++d[i][getid(a[i])][getid(b[i])];
	}
}
int get_distance(int x, int y) {
	FOR(i, 0, 2)
	FOR(j, 0, 2)
		cnt[i][j] = d[y][i][j] - (x == 0? 0 : d[x - 1][i][j]);
	if (cnt[0][1] + cnt[0][2] != cnt[1][0] + cnt[2][0]) return -1;
	if (cnt[1][0] + cnt[1][2] != cnt[0][1] + cnt[2][1]) return -1;
	if (cnt[2][0] + cnt[2][1] != cnt[0][2] + cnt[1][2]) return -1;
	int total = cnt[0][1] + cnt[0][2] + cnt[1][0] + cnt[1][2] + cnt[2][0] + cnt[2][1];
	int cnt2 = 0;
	cnt2 += min(cnt[0][1], cnt[1][0]);
	cnt2 += min(cnt[0][2], cnt[2][0]);
	cnt2 += min(cnt[1][2], cnt[2][1]);
	return total - cnt2 - (total - cnt2 * 2) / 3;
}
/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5
*/

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
dna.cpp:43:2: note: in expansion of macro 'FOR'
   43 |  FOR(i, 0, n - 1) {
      |  ^~~
dna.cpp:26:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
dna.cpp:44:3: note: in expansion of macro 'FOR'
   44 |   FOR(j, 0, 2)
      |   ^~~
dna.cpp:26:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
dna.cpp:45:3: note: in expansion of macro 'FOR'
   45 |   FOR(z, 0, 2)
      |   ^~~
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
dna.cpp:51:2: note: in expansion of macro 'FOR'
   51 |  FOR(i, 0, 2)
      |  ^~~
dna.cpp:26:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
dna.cpp:52:2: note: in expansion of macro 'FOR'
   52 |  FOR(j, 0, 2)
      |  ^~~

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