Submission #832316

#	Time	Username	Problem	Language	Result	Execution time	Memory
832316		pomuchle	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	7464 KiB

dna

#include "dna.h"
#include <ios>
#include <vector>
#include <string>
#include <cassert>
#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, p, n) for (int i=(p); i<(n); ++i)
#define sz(A) (int(A.size()))
#define V std::vector
typedef long long ll;
typedef V <int> vi;
typedef V <ll> vll;

vi ile[3][3];
void init(std::string a, std::string b) {
    a="1"+a;
    b="1"+b;
    int n=sz(a);
    REP(i, 3)
        REP(j, 3)
            ile[i][j]=vi(n+1, 0);
    static int mapa[256];
    mapa['A']=0,mapa['C']=1,mapa['T']=2;
    FOR(p, 1, n){
        REP(i, 3)
            REP(j, 3)
                ile[i][j][p]=ile[i][j][p-1];
        ++ile[mapa[a[p]]][mapa[b[p]]][p];
    }
}

int get_distance(int x, int y) {
    ++x,++y;
    V <vi> t(3, vi(3, 0));
    vi potrz(3, 0),mamy(3, 0);
    REP(i, 3)
        REP(j, 3){
            t[i][j]=i==j ? 0 : ile[i][j][y]-ile[i][j][x-1];
            potrz[j]+=t[i][j];
            mamy[i]+=t[i][j];
        }
    REP(i, 3)
        if (potrz[i]!=mamy[i])
            return -1;
    int w=0;
    REP(i, 3)
        REP(j, 3){
            int p=std::min(t[i][j], t[j][i]);
            if (p)
                w+=p,t[i][j]-=p,t[j][i]-=p;
        }
    int ilezap=0;
    REP(i, 3)
        REP(j, 3)
            ilezap+=bool(t[i][j]);
    assert(!ilezap||ilezap==3);
    REP(i, 3)
        REP(j, 3)
            if (t[i][j]){
                w+=t[i][j]*2;
                return w;
            }
    return w;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:28:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   28 |         ++ile[mapa[a[p]]][mapa[b[p]]][p];
      |                        ^
dna.cpp:28:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   28 |         ++ile[mapa[a[p]]][mapa[b[p]]][p];
      |                                    ^

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