Submission #624956

#	Time	Username	Problem	Language	Result	Execution time	Memory
624956		iomoon191	Mutating DNA (IOI21_dna)	C++17	100 / 100	37 ms	8568 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using ll = long long;
//#define int ll
using namespace std;

#define sz(x) (int)(x).size()
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define mod 998244353

#define db(x) cerr << __LINE__ << " " << #x << " " << x << "\n"
using vi = vector<int>;
using pi = pair<int, int>;

const ll N = 100005;
const ll inf = 1e18;

int cnt[N][3], sum[N][3][3];

void init(string a, string b){
	int s = sz(a);
	auto type = [&](char c){
		if(c == 'A')
			return 0;
		if(c == 'T')
			return 1;
		if(c == 'C')
			return 2;
	};
	foru(i, 1, s){
		foru(j, 0, 2){
			foru(k, 0, 2){
				sum[i][j][k] = sum[i - 1][j][k];
			}
			cnt[i][j] = cnt[i - 1][j];
		}
		sum[i][type(a[i - 1])][type(b[i - 1])]++;	
		cnt[i][type(a[i - 1])]++;
		cnt[i][type(b[i - 1])]--;
	}	
}

int get_distance(int x, int y){
	int c[3][3] = {{0}};
	foru(i, 0, 2){
		foru(j, 0, 2){
			c[i][j] = sum[y + 1][i][j] - sum[x][i][j];
		}
	}
	if(cnt[y + 1][0] != cnt[x][0] or cnt[y + 1][1] != cnt[x][1] or cnt[y + 1][2] != cnt[x][2]) return -1;
	int z, ret = 0;
	z = min(c[1][0], c[0][1]);
	c[1][0] -= z;
	c[0][1] -= z;
	ret += z;
	z = min(c[1][2], c[2][1]);
	c[1][2] -= z;
	c[2][1] -= z;
	ret += z;
	z = min(c[2][0], c[0][2]);
	c[2][0] -= z;
	c[0][2] -= z;
	ret += z;
	return ret + 2 * (c[0][1] + c[1][0]);
}

Compilation message (stderr)

dna.cpp: In lambda function:
dna.cpp:32:2: warning: control reaches end of non-void function [-Wreturn-type]
   32 |  };
      |  ^

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