Submission #714535

#	Time	Username	Problem	Language	Result	Execution time	Memory
714535		mseebacher	Mutating DNA (IOI21_dna)	C++17	22 / 100	1593 ms	4324 KiB

dna

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
#define MAXI (int)1e5
#define pb(x) push_back(x)

int s1A[(int)1e5+5];
int s1T[(int)1e5+5];
int s2A[(int)1e5+5];
int s2T[(int)1e5+5];
int falsch[(int)1e5+5];

char s1[(int)1e5+5];
char s2[(int)1e5+5];
 
void init(string x,string y){
	s1A[0] = s1T[0] = 0;
	s2A[0] = s2T[0] = falsch[0] = 0;
	int n = x.length();
	for(int i = 0;i<n;i++){
		s1[i] = x[i];
		s2[i] = y[i];
		s1A[i+1] = s1A[i];
		s2A[i+1] = s2A[i];
		s1T[i+1] = s1T[i];
		s2T[i+1] = s2T[i];
		falsch[i+1] = falsch[i];
		if(x[i] == 'A') s1A[i+1]++;
		if(y[i] == 'A') s2A[i+1]++;
		if(x[i] == 'T') s1T[i+1]++;
		if(y[i] == 'T') s2T[i+1]++;
		if(x[i] != y[i]) falsch[i+1]++;
	}
}
 
 
int get_distance(int x,int y){
	++x; ++y;
	if(s1A[y]-s1A[x-1] != s2A[y]-s2A[x-1] || s1T[y]-s1T[x-1] != s2T[y]-s2T[x-1]) return -1;
	map<pair<char,char>,int> m;
	int ans = 0;
	for(int i = x-1;i<y;i++){
		if(s1[i] == s2[i]) continue;
		if(m[{s2[i],s1[i]}] > 0){
			m[{s2[i],s1[i]}]--;
		}else{
			if(m.find({s1[i],s2[i]}) != m.end())
				m[{s1[i],s2[i]}]++;
			else m.insert({{s1[i],s2[i]},1});
			ans++;
		}
		
	} 
	return ans;
}

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