Submission #1267686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267686		Johan	Mutating DNA (IOI21_dna)	C++20	100 / 100	73 ms	8788 KiB

dna

#include "dna.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 6;
int pa[N][3], pb[N][3], p[N][3][3];
string A, B;
map < char , int > ch;
map < int , char > in;
vector < char > letters{'A', 'T', 'C'};
void init(string a, string b){
  int n = (int)a.size();
  a = '#' + a;
  b = '#' + b;
  A = a, B = b;
  ch['A'] = 0, ch['C'] = 1, ch['T'] = 2;
  in[0] = 'A', in[1] = 'C', in[2] = 'T';
  for(int i = 1; i <= n; i++){
    pa[i][ch[a[i]]]++;
    pb[i][ch[b[i]]]++;
    for(int c = 0; c < 3; c++){
      pa[i][c] += pa[i - 1][c];
      pb[i][c] += pb[i - 1][c]; 
    }
  }
  for(int i = 1; i <= n; i++){
  	p[i][ch[a[i]]][ch[b[i]]]++;
  	for(int c = 0; c < 3; c++)
  		for(int r = 0; r < 3; r++)
  			p[i][c][r] += p[i - 1][c][r];
  }
}

int get_distance(int x, int y){
  x++, y++;
  for(int i = 0; i < 3; i++){
    if(pb[y][i] - pb[x - 1][i] != pa[y][i] - pa[x - 1][i])
      return -1;
  }
  map < pair < char , char > , int > s;
  for(int i = 0; i < 3; i++){
  	for(int j = 0; j < 3; j++){
  		if(i != j)
  			s[{in[i], in[j]}] += (p[y][i][j] - p[x - 1][i][j]);
  	}
  }
  // for(auto i : letters){
  // 	for(auto j : letters){
  // 		if(s[{i, j}] > 0)
  // 			cout << i << ' ' << j << endl;
  // 	}
  // }
  // return 41234912;
  int cnt = 0;
  while(1){
  	int ok = 0;
  	for(auto i : letters){
  		for(auto j : letters){
  			if(i == j){
  				ok++;
  				continue;
  			}
  			if(s[{i, j}] == 0){
  				ok++;
  				continue;
  			}
  			// cout << i << ' ' << j << endl;
  			if(s[{j, i}] != 0){
  				if(s[{i, j}] > s[{j, i}]){
  					s[{i, j}] -= s[{j, i}];
  					cnt += s[{j, i}];
  					s[{j, i}] = 0;
  				}
  				else {
  					s[{j, i}] -= s[{i, j}];
  					cnt += s[{i, j}];
  					s[{i, j}] = 0;
  				}
  			}
  			else {
  				for(auto k : letters){
  					if(s[{j, k}] != 0){
  						if(s[{j, k}] >= s[{i, j}]){
  							s[{j, k}] -= s[{i, j}];
  							cnt += s[{i, j}];
  							s[{i, k}] += s[{i, j}];
  							s[{i, j}] = 0;
  							break;
  						}
  						else {
  							s[{i, j}] -= s[{j, k}];
  							cnt += s[{j, k}];
  							s[{i, k}] += s[{j, k}];
  						}
  					}
  				}
  			}
  		}
  	}
  	if(ok == 9)break;
  }
  return cnt;
}

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