Submission #441645

#	Time	Username	Problem	Language	Result	Execution time	Memory
441645		Gurban	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	6448 KiB

dna

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
int n,cnt[maxn][10];

void init(string a,string b){
    n = a.size();
    for(int i = 0;i < n;i++){
        if(i) for(int j = 0;j < 6;j++) cnt[i][j] = cnt[i-1][j];
        if(a[i] == 'A' and b[i] == 'T') cnt[i][0]++;
        else if(a[i] == 'T' and b[i] == 'A') cnt[i][1]++;
        else if(a[i] == 'A' and b[i] == 'C') cnt[i][2]++;
        else if(a[i] == 'C' and b[i] == 'A') cnt[i][3]++;
        else if(a[i] == 'C' and b[i] == 'T') cnt[i][4]++;
        else if(a[i] == 'T' and b[i] == 'C') cnt[i][5]++;
    }
}

int get_distance(int x,int y){
    int now[10]; memset(now,0,sizeof(now));
    for(int i = 0;i < 6;i++){
        now[i] = cnt[y][i];
        if(x-1 >= 0) now[i] -= cnt[x-1][i];
    }
    int Aa = now[0] + now[2];
    int Ab = now[1] + now[3];
    int Ta = now[1] + now[5];
    int Tb = now[0] + now[4];
    int Ca = now[3] + now[4];
    int Cb = now[2] + now[5];
    if(Aa != Ab or Ta != Tb or Ca != Cb) return -1;
    int ans = 0;
    for(int i = 0;i < 6;i += 2){
        int mn = min(now[i],now[i+1]);
        now[i] -= mn,now[i+1] -= mn;
        ans += mn;
    }
    if(now[0] > 0) ans += (now[0] * 2);
    if(now[1] > 0) ans += (now[1] * 2);
    return ans;
}

//int main(){
//
//    int n; string s,t; cin >> n >> s >> t;
//    init(n,s,t);
//    int q; cin >> q;
//    while(q--){
//        int x,y; cin >> x >> y;
//        cout<<get_distance(x,y)<<'\n';
//    }
//}

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