Submission #437166

#	Time	Username	Problem	Language	Result	Execution time	Memory
437166		flashhh	Mutating DNA (IOI21_dna)	C++17	35 / 100	53 ms	5184 KiB

dna

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define tii tuple<int,int,int>
#define fi first
#define se second
#define bp __builtin_popcount
#define nmax 100010
#define pb emplace_back

int getbit(ll x,int y)
{
    return (x>>y)&1;
}
ll getoff(ll x,int y)
{
    return x^((1ll)<<y);
}

using namespace std;

struct node
{
    int AT,AC,TA,TC,CA,CT;
    node() {}
};

int n,q;
string a,b;
node pre[nmax];

void init(string aa,string bb)
{
    a=aa; b=bb;
    n=a.length();

    for (int i=0;i<n;++i)
    {
        pre[i]=pre[i-1];
        if (a[i]=='A')
        {
            if (b[i]=='C') ++pre[i].AC;
            else if (b[i]=='T') ++pre[i].AT;
        }
        else if (a[i]=='C')
        {
            if (b[i]=='A') ++pre[i].CA;
            else if (b[i]=='T') ++pre[i].CT;
        }
        else if (a[i]=='T')
        {
            if (b[i]=='A') ++pre[i].TA;
            else if (b[i]=='C') ++pre[i].TC;
        }
    }
}
int get_distance(int x,int y)
{
    int AC=pre[y].AC-pre[x-1].AC;
    int AT=pre[y].AT-pre[x-1].AT;
    
    int CA=pre[y].CA-pre[x-1].CA;
    int CT=pre[y].CT-pre[x-1].CT;
    int TA=pre[y].TA-pre[x-1].TA;
    int TC=pre[y].TC-pre[x-1].TC;

    if (AC+AT!=CA+TA) return -1;
    if (CA+CT!=AC+TC) return -1;
    if (TA+TC!=AT+CT) return -1;

    int res=AC+AT;
    AC-=min(AC,CA); AT-=min(AT,TA);

    if (AC>0) res+=CT;
    else if (AT>0) res+=TC;

    return res;
}

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