Submission #1234692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234692		veehj	Mutating DNA (IOI21_dna)	C++17	22 / 100	1592 ms	5112 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, cnt;

void init(std::string a, std::string b) {
  map<pair<ll, pair<ll, ll>>, ll> mp;
  mp[{0, {0, 0}}] = 0;
  closest_ok.assign(a.size(), -2);
  cnt.assign(a.size(), -2);
  ll aa = 0, bb = 0, cc = 0;
  rep(i, 0, a.size()) {
    if (a[i] == 'C') aa++;
    if (a[i] == 'A') bb++;
    if (a[i] == 'T') cc++;
    if (b[i] == 'C') aa--;
    if (b[i] == 'A') bb--;
    if (b[i] == 'T') cc--;
    if (mp.find({aa, {bb, cc}}) != mp.end()) {
      closest_ok[mp[{aa, {bb, cc}}]] = i;
    }
    mp[{aa, {bb, cc}}] = i + 1;
  }
  rep(i, 0, sz(a)){
    if(closest_ok[i]==-2) continue;
    cnt[i]=0;
    if(a[i]==b[i]) continue;
    vvl v(3, vl(3, 0));
    rep(j, i, closest_ok[i]+1){
      if(a[j]==b[j]) continue;
      if(a[j]=='C') aa=0;
      if(a[j]=='A') aa=1;
      if(a[j]=='T') aa=2;
      if(b[j]=='C') bb=0;
      if(b[j]=='A') bb=1;
      if(b[j]=='T') bb=2;
      v[aa][bb]++;
    }
    rep(j, 0, 3){
      rep(k, 0, 3){
        int dist=min(v[j][k],v[k][j]);
        v[j][k]-=dist;
        v[k][j]-=dist;
        cnt[i]+=dist;
      }
    }
    cnt[i]+=(v[0][1]+v[0][2])*2;
  }
}

int get_distance(int x, int y) { 
  int can = x; int ans=0;
  while(can<=y && can!=-1){
    ans+=cnt[can];
    can=closest_ok[can]+1;
  }
  if(can==y+1) return ans;
  else return -1;
}

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