제출 #621034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
621034		Sam_a17	DNA 돌연변이 (IOI21_dna)	C++17	100 / 100	45 ms	7304 KiB

dna

#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define dbg(x) cout  << #x << " " << x << endl;
#define ll long long
#define ld long double

// template<typename T>
// void pr(vector<T>& a) {
//   for(auto i: a) {
//     cout << i << " ";
//   }
//   cout << endl;
// }
void pr(vector<pair<int, int>>& a) {
  for(auto i: a) {
    cout << "{" << i.first << "," << i.second << "}" << " ";
  }
  cout << endl;
}

void pr(vector<pair<pair<int, int>, int>>& a) {
  for(auto i: a) {
    cout << "{ {" << i.first.first << "," << i.first.second << "}" << ", " << i.second << "} ";
  }
  cout << endl;
}
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);

const int N = 2e5 + 10;
int p1[N][3], p2[N][3];
int ac[N], ca[N];
int at[N], ta[N];
int ct[N], tc[N];
int n;

void init(std::string a, std::string b) {
  n = sz(a);

  map<pair<char, char>, int> mp;
  for(int i = 0; i < n; i++) {
    p1[i + 1][0] += p1[i][0] + (a[i] == 'A');
    p1[i + 1][1] += p1[i][1] + (a[i] == 'T');
    p1[i + 1][2] += p1[i][2] + (a[i] == 'C');
  
    p2[i + 1][0] += p2[i][0] + (b[i] == 'A');
    p2[i + 1][1] += p2[i][1] + (b[i] == 'T');
    p2[i + 1][2] += p2[i][2] + (b[i] == 'C');

    ac[i + 1] = ac[i];
    ca[i + 1] = ca[i];
    at[i + 1] = at[i];
    ta[i + 1] = ta[i];
    ct[i + 1] = ct[i];
    tc[i + 1] = tc[i];

    if(a[i] == 'A' && b[i] == 'C') {
      ac[i + 1]++;
    }
    if(a[i] == 'A' && b[i] == 'T') {
      at[i + 1]++;
    }
    if(a[i] == 'C' && b[i] == 'T') {
      ct[i + 1]++;
    }
    if(a[i] == 'C' && b[i] == 'A') {
      ca[i + 1]++;
    }
    if(a[i] == 'T' && b[i] == 'A') {
      ta[i + 1]++;
    }
    if(a[i] == 'T' && b[i] == 'C') {
      tc[i + 1]++;
    }
  }
}

int get_distance(int x, int y) {
  x++, y++;
  swap(x, y);

  int a1 = p1[x][0] - p1[y - 1][0];
  int t1 = p1[x][1] - p1[y - 1][1];
  int c1 = p1[x][2] - p1[y - 1][2];

  int a2 = p2[x][0] - p2[y - 1][0];
  int t2 = p2[x][1] - p2[y - 1][1];
  int c2 = p2[x][2] - p2[y - 1][2];

  if(a1 != a2 || t1 != t2 || c1 != c2) {
    return -1;
  }
  
  int answ = 0;
  int tta = ta[x] - ta[y - 1];
  int aat = at[x] - at[y - 1];
  int mini = min(tta, aat);
  tta -= mini, aat -= mini;
  answ += mini;

  int ttc = tc[x] - tc[y - 1];
  int cct = ct[x] - ct[y - 1];
  mini = min(ttc, cct);
  answ += mini;
  cct -= mini, ttc -= mini;

  int aac = ac[x] - ac[y - 1];
  int cca = ca[x] - ca[y - 1];
  mini = min(aac, cca);
  answ += mini;
  cca -= mini, aac -= mini;

  int all_sum = aat + tta + ttc + cct + aac + cca;
  assert(all_sum % 3 == 0);

  return answ + 2 * (all_sum / 3);
}

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