Submission #438126

#TimeUsernameProblemLanguageResultExecution timeMemory
438126josiftepeMutating DNA (IOI21_dna)C++17
0 / 100
49 ms5484 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cstring> #include "dna.h" using namespace std; const int maxn = 1e5 + 5; int a_pref_sum[maxn][4]; int b_pref_sum[maxn][4]; string a, b; int n; void init(string a, string b) { memset(a_pref_sum, 0, sizeof a_pref_sum); memset(b_pref_sum, 0, sizeof b_pref_sum); n = (int) a.size(); for(int i = 0; i < n; i++) { if(a[i] == 'C') a[i] = 'B'; if(b[i] == 'C') b[i] = 'B'; } for(int i = 0; i < n; i++) { if(a[i] == 'T') a[i] = 'C'; if(b[i] == 'T') b[i] = 'C'; } ::a = a; ::b = b; int cnt_a[3] = {0, 0, 0}; int cnt_b[3] = {0, 0, 0}; for(int i = 0; i < n; i++) { int id_a = (int) (a[i] - 'A'); int id_b = (int) (b[i] - 'A'); cnt_a[id_a]++; cnt_b[id_b]++; for(int j = 0; j < 3; j++) { a_pref_sum[i][j] = cnt_a[j]; b_pref_sum[i][j] = cnt_b[j]; } } } int a_query(int &x, int &y, char c) { if(x == 0) { return a_pref_sum[y][c - 'A']; } return a_pref_sum[y][c - 'A'] - a_pref_sum[x - 1][c - 'A']; } int b_query(int &x, int &y, char c) { if(x == 0) { return b_pref_sum[y][c - 'A']; } return b_pref_sum[y][c - 'A'] - b_pref_sum[x - 1][c - 'A']; } int get_distance(int x, int y) { vector<int> v[3]; string tmp_b = b.substr(x, y - x + 1); for(int i = 0; i < tmp_b.size(); i++) { v[tmp_b[i] - 'A'].push_back(i); } int cnt[3] = {0, 0, 0}; int ret = 0; for(int i = x, j = 0; i <= y; i++, j++) { int id_a = int (a[i] - 'A'); int id_b = int (tmp_b[j] - 'A'); if(id_a != id_b) { if(cnt[id_a] + 1 >= (int) v[id_a].size()) { return -1; } swap(tmp_b[j], tmp_b[v[id_a][cnt[id_a]]]); cnt[id_a]++; ++ret; } } return ret; }

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int i = 0; i < tmp_b.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...