Submission #1005140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005140		vjudge1	Mutating DNA (IOI21_dna)	C++17	100 / 100	44 ms	7732 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

struct M {
   int v[3][3];
};
const int nmax = 1e5 + 5;
M pref[nmax];
int encr[nmax];

void init(std::string a, std::string b) {
   encr['A'] = 0;
   encr['C'] = 1;
   encr['T'] = 2;
   a = "$" + a; b = "$" + b;
   for(int i = 0; i < sz(a); i++) {
      pref[i].v[encr[a[i]]][encr[b[i]]]++;
      for(int h = 0; h < 3; h++)
         for(int j = 0; j < 3; j++)
            pref[i].v[h][j] += pref[i - 1].v[h][j];
   }
}

int get_distance(int l, int r) {
   ++l;
   ++r;
   auto A = pref[r];
   for(int i = 0; i < 3; i++)
      for(int j = 0; j < 3; j++)
         A.v[i][j] -= pref[l - 1].v[i][j];
   
   int cnt = 0;
   vector<pii> opers{make_pair(0, 1), make_pair(0, 2), make_pair(2, 1), make_pair(2, 0), make_pair(1, 0), make_pair(1, 2)};
   for(int i = 0; i < sz(opers); i++) {
      auto [x, y] = opers[i];
      if(A.v[x][y] == 0) continue;
      int a = A.v[y][x];
      if(a == 0) {
         int outra = 3 ^ x ^ y;
         int b = A.v[outra][x];
         if(b == 0) return -1;
         int total = min(A.v[x][y], b);
         A.v[x][y] -= total;
         A.v[outra][x] -= total;
         A.v[outra][y] += total;
         cnt += total;
         i--;
         continue;
      }
      else {
         int total = min(A.v[x][y], a);
         A.v[y][x] -= total;
         A.v[x][y] -= total;
         cnt += total;
         i--;
         continue;
      }
   }
   
	return cnt;
}

/**
      Istenem! Nu poate fi real.
-- Surse verificate
*/

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:28:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   28 |       pref[i].v[encr[a[i]]][encr[b[i]]]++;
      |                          ^
dna.cpp:28:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   28 |       pref[i].v[encr[a[i]]][encr[b[i]]]++;
      |                                      ^

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