Submission #658955

#	Time	Username	Problem	Language	Result	Execution time	Memory
658955		Banan	Mutating DNA (IOI21_dna)	C++17	100 / 100	49 ms	7372 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using ll = long long;
#define double long double
#define endl '\n'
#define sz(a) (int)a.size()
#define pb push_back
#define fs first
#define sc second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;

int n;
vector<int> cna(100005, 0), cnt(100005, 0), cnc(100005, 0);
vector<int> ac(100005, 0), att(100005, 0), ta(100005, 0), tc(100005, 0), ca(100005, 0), ct(100005, 0);

void init(std::string a, std::string b) {

    n=sz(a);
    for(int i=0;i<n;i++)
    {
        if(a[i]=='A'){cna[i]=cna[i-1]+1;}else{cna[i]=cna[i-1];}
        if(b[i]=='A'){cna[i]--;}

        if(a[i]=='T'){cnt[i]=cnt[i-1]+1;}else{cnt[i]=cnt[i-1];}
        if(b[i]=='T'){cnt[i]--;}

        if(a[i]=='C'){cnc[i]=cnc[i-1]+1;}else{cnc[i]=cnc[i-1];}
        if(b[i]=='C'){cnc[i]--;}

        if(a[i]=='A' && b[i]=='C'){ac[i]=ac[i-1]+1;}else{ac[i]=ac[i-1];}
        if(a[i]=='A' && b[i]=='T'){att[i]=att[i-1]+1;}else{att[i]=att[i-1];}

        if(a[i]=='T' && b[i]=='A'){ta[i]=ta[i-1]+1;}else{ta[i]=ta[i-1];}
        if(a[i]=='T' && b[i]=='C'){tc[i]=tc[i-1]+1;}else{tc[i]=tc[i-1];}

        if(a[i]=='C' && b[i]=='A'){ca[i]=ca[i-1]+1;}else{ca[i]=ca[i-1];}
        if(a[i]=='C' && b[i]=='T'){ct[i]=ct[i-1]+1;}else{ct[i]=ct[i-1];}
    }
}

int get_distance(int x, int y) {
    int ans=0;
    if(x==0)
    {
        if(cna[y]!=0 || cnt[y]!=0 || cnc[y]!=0){return -1;}
        if(cna[y]-cna[x-1]!=0 || cnt[y]-cnt[x-1]!=0 || cnc[y]-cnc[x-1]!=0){return -1;}
        ans+=min(ca[y], ac[y]);
        ans+=min(ta[y], att[y]);
        ans+=min(tc[y], ct[y]);
        vector<int> v(3);
        v[0]=max(ca[y], ac[y])-min(ca[y], ac[y]);
        v[1]=max(ta[y], att[y])-min(ta[y], att[y]);
        v[2]=max(tc[y], ct[y])-min(tc[y], ct[y]);
        sort(all(v));
        ans+=v[0]+v[1];
    }
    else
    {
        if(cna[y]-cna[x-1]!=0 || cnt[y]-cnt[x-1]!=0 || cnc[y]-cnc[x-1]!=0){return -1;}
        ans+=min(ca[y]-ca[x-1], ac[y]-ac[x-1]);
        ans+=min(ta[y]-ta[x-1], att[y]-att[x-1]);
        ans+=min(tc[y]-tc[x-1], ct[y]-ct[x-1]);
        vector<int> v(3);
        v[0]=max(ca[y]-ca[x-1], ac[y]-ac[x-1])-min(ca[y]-ca[x-1], ac[y]-ac[x-1]);
        v[1]=max(ta[y]-ta[x-1], att[y]-att[x-1])-min(ta[y]-ta[x-1], att[y]-att[x-1]);
        v[2]=max(tc[y]-tc[x-1], ct[y]-ct[x-1])-min(tc[y]-tc[x-1], ct[y]-ct[x-1]);
        sort(all(v));
        ans+=v[0]+v[1];
    }
    return ans;
}

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