Submission #641513

#	Time	Username	Problem	Language	Result	Execution time	Memory
641513		ymm	Mutating DNA (IOI21_dna)	C++17	100 / 100	35 ms	7324 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

static const int N = 100'010;
static int ps[N][3][3];


void init(std::string a, std::string b)
{
	Loop (i,0,a.size()) {
		int x = a[i]=='A'? 0: a[i]=='T'? 1: 2;
		int y = b[i]=='A'? 0: b[i]=='T'? 1: 2;
		ps[i+1][x][y] = 1;
		Loop (j,0,3) Loop (k,0,3)
			ps[i+1][j][k] += ps[i][j][k];
	}
}

int get_distance(int l, int r)
{
	++r;
	int a[3][3];
	Loop (i,0,3) Loop (j,0,3)
		a[i][j] = ps[r][i][j] - ps[l][i][j];
	int ans = 0;
	Loop (i,0,3) Loop (j,i+1,3) {
		int mn = min(a[i][j], a[j][i]);
		ans += mn;
		a[i][j] -= mn;
		a[j][i] -= mn;
	}
	if (a[0][1] != a[1][2] || a[1][2] != a[2][0])
		return -1;
	if (a[0][2] != a[2][1] || a[2][1] != a[1][0])
		return -1;
	ans += 2 * a[0][1];
	ans += 2 * a[1][0];
	return ans;
}

Compilation message (stderr)

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

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