Submission #758211

#	Time	Username	Problem	Language	Result	Execution time	Memory
758211		JANCARAPAN	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	10956 KiB

dna

#include <bits/stdc++.h>
using namespace std;  
#define ll long long
#define fi first
#define se second
#define sz(a) (long long) a.size()
//#define endl '\n'

const long long INF = 1e18, MOD = 1e9+7; 

vector<vector<int>> pref;

int get_distance(int l, int r) {
  int aa = pref[r + 1][0] - pref[l][0], ab = pref[r + 1][1] - pref[l][1], ac = pref[r + 1][2] - pref[l][2];
  int ba = pref[r + 1][3] - pref[l][3], bb = pref[r + 1][4] - pref[l][4], bc = pref[r + 1][5] - pref[l][5];
  int ca = pref[r + 1][6] - pref[l][6], cb = pref[r + 1][7] - pref[l][7], cc = pref[r + 1][8] - pref[l][8];
  
  if (ab + ac != ba + ca or ba + bc != ab + cb or ca + cb != ac + bc) return -1;
  
  int x = min(ab, ba), y = min(ac, ca), z = min(bc, cb);
  
  int ans = x + y + z;
  
  ab -= x; ba -= x;
  ac -= y; ca -= y;
  bc -= z; cb -= z;
  
  int left = ab + ba + ac + ca + bc + cb;
  assert(left % 3 == 0);
  ans += max(0, ab + ba + ac + ca + bc + cb) / 3 * 2;
  
  return ans;
}

void init(string a, string b) {
  int n = a.size();
  for (int i = 0; i < n; i++) {
    if (a[i] == 'T') a[i] = 'B';
    if (b[i] == 'T') b[i] = 'B';
  }
  pref = vector<vector<int>> (n + 1, vector<int>(9)); // 0 = A-A, 1 = A-B, 2 = A-C, 3 = B-B...
  
  for (int i = 0; i < n; i++) {
    pref[i + 1][3*(a[i]-'A')+(b[i]-'A')] += 1;
    for (int j = 0; j < 9; j++) {
      pref[i + 1][j] += pref[i][j];
    }
  }
  
  //cout << get_distance(1, 3) << endl;
  //cout << get_distance(4, 5) << endl;
  //cout << get_distance(3, 5) << endl;
}




//signed main() {
  //ios_base::sync_with_stdio(false);
  //cin.tie(0);
  //int tt = 1;
  //cin >> tt;
  //while (tt--) {
    //init("ATACAT", "ACTATA");
  //}
  //return 0;
//}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:14:7: warning: unused variable 'aa' [-Wunused-variable]
   14 |   int aa = pref[r + 1][0] - pref[l][0], ab = pref[r + 1][1] - pref[l][1], ac = pref[r + 1][2] - pref[l][2];
      |       ^~
dna.cpp:15:41: warning: unused variable 'bb' [-Wunused-variable]
   15 |   int ba = pref[r + 1][3] - pref[l][3], bb = pref[r + 1][4] - pref[l][4], bc = pref[r + 1][5] - pref[l][5];
      |                                         ^~
dna.cpp:16:75: warning: unused variable 'cc' [-Wunused-variable]
   16 |   int ca = pref[r + 1][6] - pref[l][6], cb = pref[r + 1][7] - pref[l][7], cc = pref[r + 1][8] - pref[l][8];
      |                                                                           ^~

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