Submission #441376

#	Time	Username	Problem	Language	Result	Execution time	Memory
441376		mariowong	Mutating DNA (IOI21_dna)	C++17	0 / 100	51 ms	7028 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

using namespace std;

int ct[100005][5],ct2[100005][5],n,ans[100005];
priority_queue <int> q[5];
char dd[5]={'A','C','T'};
void init(std::string a, std::string b) {
    n=a.length();
    for (int i=0;i<n;i++){
        for (int j=0;j<3;j++){
            if (i!=0){
                
            ct[i][j]=ct[i-1][j];
            ct2[i][j]=ct2[i-1][j];
            }
            if (a[i] == dd[j]){
                ct[i][j]++;
                q[j].push(-i);
            }
            if (b[i] == dd[j])
            ct2[i][j]++;
        }
    }
    for (int i=0;i<n;i++){
        if (i!= 0)
        ans[i]=ans[i-1];
        for (int j=0;j<3;j++){
            if (!q[j].empty() && q[j].top() == -i){
                if (dd[j] == b[i]){
                    q[j].pop();
                    break;
                }
                for (int k=0;k<3;k++){
                    if (b[i] == dd[k]){
                        q[k].pop();
                        q[k].push(q[j].top());
                        q[j].pop();
                        ans[i]++;
                    }
                }
            }
        }
    }
}

int get_distance(int x, int y) {
    for (int i=0;i<3;i++){
        if (ct[y][i]-ct[x-1][i] != ct2[y][i]-ct2[x-1][i])
        return -1;
    }
    return ans[y]-ans[x-1];
}

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