Submission #480990

#	Time	Username	Problem	Language	Result	Execution time	Memory
480990		SAAD	Mutating DNA (IOI21_dna)	C++17	0 / 100	40 ms	7172 KiB

dna

#define F first
#define S second
#define rep(i,a,b) for(int i=a;!(a==b&&i!=b)&&((i<=b&&b>=a)||(i>=b&&a>=b));i+=(a<=b?1:-1))
#define pb push_back
#define Fbitl __builtin_ffs
#define bit1 __builtin_popcount
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
int idx[100003][3][3] , n , ch[200] , A[100002][2] , T[100002][2] ;
void init(string a , string b ) {
	memset(idx,0,sizeof(idx));
	memset(A, 0, sizeof(A));
	memset(T, 0, sizeof(T));
	n = a.length();
	ch['T'] = 1;
	ch['C'] = 2;
	for (int i = 0; i < n; i++) {
		if (a[i] == 'A')A[i][0]++;
		if(a[i]=='T')T[i][0]++;
		if (b[i] == 'A')A[i][1]++;
		if (b[i] == 'T')T[i][1]++;
		a[i] = ch[a[i]]; b[i] = ch[b[i]];
		idx[i][a[i]][b[i]]++;
		if (i) {
			A[i][0] += A[i - 1][0]; A[i][1] += A[i - 1][1];
			T[i][0] += T[i - 1][0]; T[i][1] += T[i - 1][1];
			for (int j = 0; j < 3;j++) {
				for (int o = 0; o < 3; o++) {
					idx[i][j][o] += idx[i-1][j][o];
				}
			}
		}
	}
}
int get_distance(int x, int y) {
	if (A[y][0] - (x ? A[x - 1][0] : 0) != A[y][1] - (x ? A[x - 1][1] : 0))return -1;
	if (T[y][0] - (x ? T[x - 1][0] : 0) != T[y][1] - (x ? T[x - 1][1] : 0))return -1;
	int anoth = 0;
	int res = 0;
	for (int i = 0; i < 3; i++ ) {
		for (int j = i; j < 3; j++ ) {
			if (i == j) continue;
			int c1 = idx[y][i][j] - (x ? idx[x][i][j] : 0);
			int c2 = idx[y][j][i] - (x ? idx[x][j][i] : 0);
			res += min(c1,c2);
			anoth += max(c1, c2) - min(c1, c2);
		}
	}
	return res + ( (anoth/3) * 2 );
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:39:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |   a[i] = ch[a[i]]; b[i] = ch[b[i]];
      |                 ^
dna.cpp:39:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |   a[i] = ch[a[i]]; b[i] = ch[b[i]];
      |                                  ^
dna.cpp:40:14: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |   idx[i][a[i]][b[i]]++;
      |              ^
dna.cpp:40:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |   idx[i][a[i]][b[i]]++;
      |                    ^

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