Submission #1122589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122589		I_FloPPed21	Mutating DNA (IOI21_dna)	C++20	0 / 100	1596 ms	8000 KiB

dna

#include <iostream>
using namespace std;
const int N=1e5+5;
int sp_a[N],sp_b[N];
int a1[N],b1[N],c1[N];
int a2[N],b2[N],c2[N];
int difs[N][3][3];

int get_distance(int x,int y)
{
    x++,y++;
    if((a1[y]-a1[x-1])!=(a2[y]-a2[x-1]))
        return -1;
    if((b1[y]-b1[x-1])!=(b2[y]-b2[x-1]))
        return -1;
    if((c1[y]-c1[x-1])!=(c2[y]-c2[x-1]))
        return -1;
    int rem=0;

    int sp=0,ans=0;
    for(int i=1;i<=3;i++)
    {
        for(int j=i+1;j<=3;j++)
        {
            int cost1=difs[y][i][j]-difs[x-1][i][j];
            int cost2=difs[y][j][i]-difs[x-1][j][i];
            ans+=min(cost1,cost2)/2;
            sp+=abs(cost1-cost2);
        }
    }
    return ans+(sp)/3*2;
}
void init(string a,string b)
{
    a="#"+a;
    b="#"+a;
    int d=a.size();
    for(int i=1; i<=d; i++)
    {
        a1[i]+=a1[i-1];
        a2[i]+=a[i-1];
        b1[i]+=b1[i-1];
        b2[i]+=b2[i-1];
        c1[i]+=a1[i-1];
        c2[i]+=a2[i-1];

        if(a[i]=='A')
            a1[i]++;
        if(a[i]=='B')
            b1[i]++;
        if(a[i]=='T')
            c1[i]++;

        if(b[i]=='A')
            a2[i]++;
        if(b[i]=='B')
            b2[i]++;
        if(b[i]=='T')
            c2[i]++;
        for(int j=1; j<=3; j++)
            for(int k=1; k<=3; k++)
                difs[i][j][k]+=difs[i-1][j][k];
        if(a[i]!=b[i])
        {
            int cons1=0,cons2=0;
            if(a[i]=='A')
                cons1=1;
            else if(a[i]=='b')
                cons1=2;
            else
                cons1=3;

            if(b[i]=='A')
                cons2=1;
            else if(b[i]=='B')
                cons2=2;
            else
                cons2=3;
            difs[i][cons1][cons2]++;
        }
    }
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:62:30: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   62 |                 difs[i][j][k]+=difs[i-1][j][k];
      |                 ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
dna.cpp:61:27: note: within this loop
   61 |             for(int k=1; k<=3; k++)
      |                          ~^~~

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