Submission #720863

#	Time	Username	Problem	Language	Result	Execution time	Memory
720863		spike1236	Mutating DNA (IOI21_dna)	C++17	71 / 100	1573 ms	7080 KiB

dna

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
#define ld long double
#define all(_v) _v.begin(), _v.end()
#define sz(_v) (int)_v.size()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define veci vector <int>
#define vecll vector <ll>

// template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double PI = 3.141592653589793;
const double eps = 1e-9;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;

const int MAXN = 1e5 + 10;
int cnt[MAXN][3][3];

void init(string a, string b) {
    for(int i = 0; i < a.size(); ++i) {
        int x = 0 ,y = 0;
        if(a[i] == 'A') x = 0;
        if(a[i] == 'C') x = 1;
        if(a[i] == 'T') x = 2;
        if(b[i] == 'A') y = 0;
        if(b[i] == 'C') y = 1;
        if(b[i] == 'T') y = 2;
        cnt[i + 1][x][y]++;
        for(int j = 0; j < 3; ++j) for(int k = 0; k < 3; ++k) cnt[i + 1][j][k] += cnt[i][j][k];
    }
}

int get_distance(int x, int y) {
    ++x;
    ++y;
    int a[3][3];
    for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) a[i][j] = cnt[y][i][j] - cnt[x - 1][i][j];
    for(int i = 0; i < 3; ++i) {
        if(a[i][0] + a[i][1] + a[i][2] != a[0][i] + a[1][i] + a[2][i]) return -1;
    }
    int res = 0;
    // cout << x << ' ' << y << ":\n";
    // for(int i = 0; i < 3; ++i) {
    //     for(int j = 0; j < 3; ++j) {
    //         cout << a[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    for(int i = 0; i < 3; ++i) {
        for(int j = 0; j < 3; ++j) {
            if(i == j) continue;
            while(a[i][j] > 0 && a[j][i] > 0) {
                a[i][j]--;
                a[j][i]--;
                a[i][i]++;
                a[j][j]++;
                ++res;
            }
        }
    }
    int cn = 0;
    for(int i = 0; i < 3; ++i) {
        for(int j = 0; j < 3; ++j) {
            if(i == j) continue;
            cn += a[i][j];
        }
    }
    // cout << "-----\n";
    // for(int i = 0; i < 3; ++i) {
    //     for(int j = 0; j < 3; ++j) {
    //         cout << a[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    return res + 2 * cn / 3;
}

// void solve() {
//     init("ATACAT", "ACTATA");
//     cout << get_distance(1, 3) << '\n';
//     cout << get_distance(4, 5) << '\n';
//     cout << get_distance(3, 5) << '\n';
//     cout << get_distance(1, 5) << '\n';
// }

// int main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);
//     int CNT_TESTS = 1;
//     // cin >> CNT_TESTS;
//     for(int NUMCASE = 1; NUMCASE <= CNT_TESTS; ++NUMCASE) {
//         solve();
//         if(NUMCASE != CNT_TESTS) cout << '\n';
//     }
//     return 0;
// }

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i = 0; i < a.size(); ++i) {
      |                    ~~^~~~~~~~~~

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