Submission #538232

#	Time	Username	Problem	Language	Result	Execution time	Memory
538232		MrTEK	DNA 돌연변이 (IOI21_dna)	C++17	0 / 100	75 ms	9868 KiB

dna

#include "dna.h"
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <climits>
#include <ctime>
 
 
using namespace std;
 
const int N = 1e5 + 5;

char s1[N],s2[N];
int n;


int f(int x,int y) {
	if (s1[x] == 'a' && s2[y] == 't')
		return 0;
	if (s1[x] == 't' && s2[y] == 'a')
		return 1;
	if (s1[x] == 'a' && s2[y] == 'c')
		return 2;
	if (s1[x] == 'c' && s2[y] == 'a')
		return 3;
	if (s1[x] == 'c' && s2[y] == 't')
		return 4;
	if (s1[x] == 't' && s2[y] == 'c')
		return 5;
	return -1;
}

struct node {
	int cnt[6];

    node operator+(node oth) {
    	node res;

    	for (int i = 0 ; i < 6 ; i++)
    		res.cnt[i] = cnt[i] + oth.cnt[i];

    	int simplify01 = min(res.cnt[0],res.cnt[1]);
    	int simplify23 = min(res.cnt[2],res.cnt[3]);
    	int simplify45 = min(res.cnt[4],res.cnt[5]);

    	res.cnt[0] -= simplify01;
    	res.cnt[1] -= simplify01;
    	res.cnt[2] -= simplify23;
    	res.cnt[3] -= simplify23;
    	res.cnt[4] -= simplify45;
    	res.cnt[5] -= simplify45;
    	return res;
    }

}tree[N<<2],zero;


void init_tree(int ind,int l,int r) {

	if (l == r) {
		tree[ind].cnt[f(l,r)] = 1;
		return;
	}

	int mid = (l + r) / 2;

	init_tree(ind + ind,l,mid);
	init_tree(ind + ind + 1,mid + 1,r);

	tree[ind] = tree[ind + ind] + tree[ind + ind + 1];

}

void init(std::string a, std::string b) {
	n = a.size();
	for (int i = 0 ; i < a.size() ; i++)
		s1[i + 1] = a[i];

	for (int i = 0 ; i < b.size() ; i++)
		s2[i + 1] = a[i];

	init_tree(1,1,n);
}

node query(int ind,int l,int r,int lw,int rw) {
	if (l > rw || r < lw)
		return zero;

	if (l >= lw && r <= rw)
		return tree[ind];

	int mid = (l + r) / 2;
	return query(ind + ind,l,mid,lw,rw) + query(ind + ind + 1,mid + 1,r,lw,rw);
}

int get_distance(int x, int y) {

	x++;
	y++;
	node res = query(1,1,n,x,y);

	if (res.cnt[0]) {
		if (res.cnt[0] == res.cnt[5] && res.cnt[5] == res.cnt[3])
			return res.cnt[0];
		return -1;
	}

	else {
		if (res.cnt[1] == res.cnt[4] && res.cnt[4] == res.cnt[2])
			return res.cnt[1];
		return -1;
	}

	return 0;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for (int i = 0 ; i < a.size() ; i++)
      |                   ~~^~~~~~~~~~
dna.cpp:90:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (int i = 0 ; i < b.size() ; i++)
      |                   ~~^~~~~~~~~~

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