Submission #1234717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234717		veehj	Mutating DNA (IOI21_dna)	C++17	100 / 100	107 ms	33304 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define rrep(i, a, b) for (ll i = a; i >= b; i--)
#define vl vector<ll>
#define vpll vector<pair<ll, ll>>
#define vvl vector<vector<ll>>
#define pll pair<ll, ll>
vl closest_ok;
vector<vvl> mis, no;

void init(std::string a, std::string b) {
  no.assign(2, vvl(sz(a), vl(3, 0)));
  mis.assign(a.size(), vvl(3, vl(3, 0)));
  rep(i, 0, sz(a)){
    if(i!=0) mis[i]=mis[i-1];
    if(i!=0){
      no[0][i]=no[0][i-1];
      no[1][i]=no[1][i-1];
    }
    if(a[i]==b[i]) continue;
    int aa=0, bb=0;
    if(a[i]=='A') aa=1;
    if(a[i]=='T') aa=2;
    if(b[i]=='A') bb=1;
    if(b[i]=='T') bb=2;
    no[0][i][aa]++;
    no[1][i][bb]++;
    mis[i][aa][bb]++;
  }
}

int get_distance(int x, int y) { 
  vvl cnt=mis[y];
  if(x!=0){
    rep(i, 0, 3){
      if(no[0][y][i]-no[0][x-1][i]!=no[1][y][i]-no[1][x-1][i]){
        return -1;
      }
      rep(j, 0, 3){
        cnt[i][j]-=mis[x-1][i][j];
      }
    }
  } else {
    rep(i, 0, 3){
      if(no[0][y][i]!=no[1][y][i]){
        return -1;
      }
    }
  }
  ll ans=0;
  rep(i, 0, 3){
    rep(j, 0, 3){
      ll dist=min(cnt[i][j], cnt[j][i]);
      ans+=dist;
      cnt[i][j]-=dist;
      cnt[j][i]-=dist;
    }
  }
  ans+=(cnt[0][1]+cnt[0][2])*2;
  return ans;
}

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