Submission #917127

#	Time	Username	Problem	Language	Result	Execution time	Memory
917127		pan	Mutating DNA (IOI21_dna)	C++17	35 / 100	73 ms	29316 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#include <string>
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
vector<ll> one, two;
vector<vector<ll> > single;
vector<vector<vector<ll> > > duo;
void init(string a, string b)
{
	ll n = a.length();
	//show(1);
	one.resize(n); two.resize(n); single.assign(n+1, vector<ll>(3, 0)); duo.assign(n+1, vector<vector<ll> > (3,  vector<ll>(3,0)));
	//show(1);
	for (ll i=0; i<a.length(); ++i)
	{
		if (a[i]=='A') one[i] = 0;
		if (a[i]=='C') one[i] = 1;
		if (a[i]=='T') one[i] = 2;
		if (b[i]=='A') two[i] = 0;
		if (b[i]=='C') two[i] = 1;
		if (b[i]=='T') two[i] = 2;
		for (ll j=0; j<3; ++j) single[i+1][j] = single[i][j];
		single[i+1][one[i]]++;
		single[i+1][two[i]]--;
		for (ll x=0; x<3; ++x) for (ll j=0; j<3; ++j) duo[i+1][x][j] = duo[i][x][j];
		duo[i+1][one[i]][two[i]]++;
		
	}
	//for (ll i=0; i<n; ++i) for (ll j=0; j<3; ++j) show3(i+1, j, single[i+1][j])

	
}
int get_distance(int x, int y)
{
	//show2(x, y);
	y++;
	for (ll i=0; i<3; ++i) 
	{
		//show(single[y][i] - single[x][i]);
		if (single[y][i] - single[x][i]!=0) return -1;
	}
	ll ans = 0;
	ll tem1 = duo[y][0][1] - duo[x][0][1];
	ll tem2 = duo[y][1][0] - duo[x][1][0];
	ans+=min(tem1, tem2);
	tem1-=min(tem1, tem2);
	tem2-=min(tem1, tem2);
	ans += 2*(tem1+tem2);
	tem1 = duo[y][1][2]-duo[x][1][2];
	tem2 = duo[y][2][1]-duo[x][2][1];
	ans+=min(tem1, tem2);
	tem1 = duo[y][0][2]-duo[x][0][2];
	tem2 = duo[y][2][0]-duo[x][2][0];
	ans+=min(tem1, tem2);
	return ans;
}

Compilation message (stderr)

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

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