Submission #985925

#	Time	Username	Problem	Language	Result	Execution time	Memory
985925		LucaIlie	Mutating DNA (IOI21_dna)	C++17	100 / 100	28 ms	6492 KiB

dna

#include "dna.h"
#include <iostream>
using namespace std;
#define nmax 100001

int n;
int AtoT[nmax], AtoC[nmax], TtoA[nmax], TtoC[nmax], CtoA[nmax], CtoT[nmax];
int valAtoT, valAtoC, valTtoA, valTtoC, valCtoA, valCtoT;
string A, B;
void init( string a, string b ) {
    int i;
    n = a.size();
    A = a;
    B = b;
    a = '0' + a;
    b = '0' + b;
    for( i = 1; i <= n; i++ ) {
        AtoT[i] = AtoT[i - 1];
        AtoC[i] = AtoC[i - 1];
        TtoA[i] = TtoA[i - 1];
        TtoC[i] = TtoC[i - 1];
        CtoA[i] = CtoA[i - 1];
        CtoT[i] = CtoT[i - 1];
        if( a[i] == b[i] )
            continue;
        if( a[i] == 'A' ) {
            if( b[i] == 'T' )
                AtoT[i]++;
            else
                AtoC[i]++;
        } else if( a[i] == 'C' ) {
            if( b[i] == 'T' )
                CtoT[i]++;
            else
                CtoA[i]++;
        } else {
            if( b[i] == 'A' )
                TtoA[i]++;
            else
                TtoC[i]++;
        }
    }
}

int get_distance( int x, int y ) {
    int minn, rez = 0;
    x++;
    y++;
    valAtoC = AtoC[y] - AtoC[x - 1];
    valAtoT = AtoT[y] - AtoT[x - 1];
    valTtoC = TtoC[y] - TtoC[x - 1];
    valTtoA = TtoA[y] - TtoA[x - 1];
    valCtoA = CtoA[y] - CtoA[x - 1];
    valCtoT = CtoT[y] - CtoT[x - 1];

    minn = min( valAtoC, valCtoA );
    valAtoC -= minn;
    valCtoA -= minn;
    rez += minn;

    minn = min( valAtoT, valTtoA );
    valAtoT -= minn;
    valTtoA -= minn;
    rez += minn;

    minn = min( valCtoT, valTtoC );
    valCtoT -= minn;
    valTtoC -= minn;
    rez += minn;

    //cout << "rez " << rez << "\n";
    if( valCtoA == valAtoT && valAtoT == valTtoC && valCtoT == valTtoA && valTtoA == valAtoC )
        return rez + 2 * valCtoA + 2 * valAtoC;
    return -1;
}

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