Submission #577483

#	Time	Username	Problem	Language	Result	Execution time	Memory
577483		keta_tsimakuridze	Mutating DNA (IOI21_dna)	C++17	100 / 100	83 ms	7380 KiB

dna

#include "dna.h"'
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int tree[N][3][3], n;
void upd(int id, int t1, int t2) {
	++id;
	for(id; id <= n; id += id & (-id)) tree[id][t1][t2] ++;
}
int get(int id, int t1, int t2) {
	++id;
	int ans = 0;
	for(id; id >= 1; id -= id & (-id)) ans += tree[id][t1][t2];
	return ans;
}
void init(std::string a, std::string b) {
	n = a.size();
	for(int i = 0; i < n; i++) {
		upd(i, (a[i] == 'A' ? 1 : a[i] == 'C' ? 0 : 2), (b[i] == 'A' ? 1 : b[i] == 'C' ? 0 : 2));
	}
}

int get_distance(int x, int y) {
	vector<vector<int> > a;
	a.resize(3, vector<int> (3));	
	int ans = 0;
	vector<int> X(3);
	
	for(int t1 = 0; t1 < 3; t1++) {
		for(int t2 = 0; t2 < 3; t2++) {
			a[t1][t2] = get(y, t1, t2) - get(x - 1, t1, t2);
			X[t2] += a[t1][t2];
			X[t1] -= a[t1][t2];
		}
	}
	
	for(int t1 = 0; t1 < 3; t1++) {
		if(X[t1]) return -1;
	}
	for(int t1 = 0; t1 < 3; t1++) {
		for(int t2 = t1 + 1; t2 < 3; t2++) {
			int xx = min(a[t1][t2], a[t2][t1]);
			a[t1][t2] -= xx;
			a[t2][t1] -= xx; 
			ans += xx;
		}
	}
	int cn = 0;
	for(int t1 = 0; t1 < 3; t1++) {
		for(int t2 = 0; t2 < 3; t2++) {
			if(t1 == t2) continue;
			cn += a[t1][t2];
		}
	} 
	return cn / 3 * 2 + ans;
}
/*
int main() {
	int n, q;
	assert(scanf("%d %d", &n, &q) == 2);
	char A[n+1], B[n+1];
	assert(scanf("%s", A) == 1);
	assert(scanf("%s", B) == 1);
	std::string a = std::string(A);
	std::string b = std::string(B);
	std::vector<int> x(q), y(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d %d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);
	std::vector<int> results(q);
	init(a, b);
	for (int i = 0; i < q; i++) {
		results[i] = get_distance(x[i], y[i]);
	}
	for (int i = 0; i < q; i++) {
		printf("%d\n", results[i]);
	}
	fclose(stdout);
	return 0;
}*/

Compilation message (stderr)

dna.cpp:1:17: warning: missing terminating ' character
    1 | #include "dna.h"'
      |                 ^
dna.cpp:1:17: warning: extra tokens at end of #include directive
dna.cpp: In function 'void upd(int, int, int)':
dna.cpp:8:6: warning: statement has no effect [-Wunused-value]
    8 |  for(id; id <= n; id += id & (-id)) tree[id][t1][t2] ++;
      |      ^~
dna.cpp: In function 'int get(int, int, int)':
dna.cpp:13:6: warning: statement has no effect [-Wunused-value]
   13 |  for(id; id >= 1; id -= id & (-id)) ans += tree[id][t1][t2];
      |      ^~

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