Submission #439190

#	Time	Username	Problem	Language	Result	Execution time	Memory
439190		haojiandan	Mutating DNA (IOI21_dna)	C++17	100 / 100	63 ms	6144 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=(5e5)+10;
int s[maxn][6],n;
int cnt[maxn][3];
int id[300][300],dy[300];
void init(string a,string b) {
	n=a.size();
	dy['A']=0,dy['C']=1,dy['T']=2;
	id['C']['A']=0,id['A']['T']=2,id['A']['C']=4;
	id['T']['A']=1,id['C']['T']=3,id['T']['C']=5;
	for (int i=1;i<=n;i++) {
		for (int j=0;j<6;j++) s[i][j]=s[i-1][j];
		if (a[i-1]!=b[i-1]) {
			s[i][id[a[i-1]][b[i-1]]]++;
		}
		for (int j=0;j<3;j++) cnt[i][j]=cnt[i-1][j];
		cnt[i][dy[a[i-1]]]++;
		cnt[i][dy[b[i-1]]]--;
	}
}

int get_distance(int x, int y) {
	int d[10];
	for (int i=0;i<3;i++) if (cnt[y+1][i]!=cnt[x][i]) return -1;
	for (int i=0;i<6;i++) d[i]=s[y+1][i]-s[x][i];
	int ans=0,t=min(d[0],d[4]);
	d[0]-=t,d[4]-=t,ans+=t;
	t=min(d[2],d[1]),d[1]-=t,d[2]-=t,ans+=t;
	t=min(d[3],d[5]),d[3]-=t,d[5]-=t,ans+=t;
//	printf("%d %d %d\n",d[0]+d[4],d[1]+d[2],d[3]+d[5]);
	return ans+(d[3]+d[5])*2;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:16:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   16 |    s[i][id[a[i-1]][b[i-1]]]++;
      |                  ^
dna.cpp:16:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   16 |    s[i][id[a[i-1]][b[i-1]]]++;
      |                          ^
dna.cpp:19:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   19 |   cnt[i][dy[a[i-1]]]++;
      |                   ^
dna.cpp:20:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |   cnt[i][dy[b[i-1]]]--;
      |                   ^

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