Submission #439296

#	Time	Username	Problem	Language	Result	Execution time	Memory
439296		Waratpp123	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	8148 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int cnta[100010],cntc[100010],cntt[100010],cnta2[100010],cntc2[100010],cntt2[100010];
int cntat[100010],cntta[100010],cnttc[100010],cntct[100010],cntac[100010],cntca[100010];
void init(string a, string b) {
    int n,i;
    n=a.size();
    for(i=0;i<n;i++){
        if(a[i]=='A') cnta[i+1]++;
        else if(a[i]=='C') cntc[i+1]++;
        else cntt[i+1]++;
        if(b[i]=='A') cnta2[i+1]++;
        else if(b[i]=='C') cntc2[i+1]++;
        else cntt2[i+1]++;
        cnta[i+1]+=cnta[i];
        cntc[i+1]+=cntc[i];
        cntt[i+1]+=cntt[i];
        cnta2[i+1]+=cnta2[i];
        cntc2[i+1]+=cntc2[i];
        cntt2[i+1]+=cntt2[i];
    }
    for(i=0;i<n;i++){
        if(a[i]=='A'&&b[i]=='C') cntac[i+1]++;
        else if(a[i]=='A'&&b[i]=='T') cntat[i+1]++;
        else if(a[i]=='C'&&b[i]=='A') cntca[i+1]++;
        else if(a[i]=='C'&&b[i]=='T') cntct[i+1]++;
        else if(a[i]=='T'&&b[i]=='A') cntta[i+1]++;
        else if(a[i]=='T'&&b[i]=='C') cnttc[i+1]++;
        cntac[i+1]+=cntac[i];
        cntct[i+1]+=cntct[i];
        cntta[i+1]+=cntta[i];
        cntat[i+1]+=cntat[i];
        cntca[i+1]+=cntca[i];
        cnttc[i+1]+=cnttc[i];
    }
}

int get_distance(int x, int y) {
    x++,y++;
    int l,r;
    if(cnta[y]-cnta[x-1]!=cnta2[y]-cnta2[x-1]) return -1;
    if(cntc[y]-cntc[x-1]!=cntc2[y]-cntc2[x-1]) return -1;
    if(cntt[y]-cntt[x-1]!=cntt2[y]-cntt2[x-1]) return -1;
	return  min(cntat[y]-cntat[x-1],cntta[y]-cntta[x-1])+
            min(cntac[y]-cntac[x-1],cntca[y]-cntca[x-1])+
            min(cntct[y]-cntct[x-1],cnttc[y]-cnttc[x-1])+
            2*(max(cntat[y]-cntat[x-1],cntta[y]-cntta[x-1])-
               min(cntat[y]-cntat[x-1],cntta[y]-cntta[x-1]));
}
/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5
*/

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:41:9: warning: unused variable 'l' [-Wunused-variable]
   41 |     int l,r;
      |         ^
dna.cpp:41:11: warning: unused variable 'r' [-Wunused-variable]
   41 |     int l,r;
      |           ^

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