oj.uz

Submission #939870

# Submission time Handle Problem Language Result Execution time Memory
939870 2024-03-06T22:06:20 Z vladilius Mutating DNA (IOI21_dna) C++17
71 / 100
 1500 ms 2396 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<char, char>;

string a, b;
vector<char> x = {'A', 'C', 'T'};

void init(string as, string bs){
    a = as; b = bs;
}

int get_distance(int l, int r){
    map<char, int> mp;
    for (int i = l; i <= r; i++){
        mp[a[i]]++;
        mp[b[i]]--;
    }
    for (auto t: mp){
        if (t.second != 0){
            return -1;
        }
    }
    map<pii, int> cnt;
    for (int i = l; i <= r; i++){
        if (a[i] == b[i]) continue;
        cnt[{a[i], b[i]}]++;
    }
    vector<pii> arr;
    for (auto [u, v]: cnt){
        arr.push_back(u);
    }
    int out = 0;
    for (auto p1: arr){
        pii p2 = {p1.second, p1.first};
        if (cnt.find(p2) == cnt.end()){
            continue;
        }
        int k1 = cnt[p1], k2 = cnt[p2];
        out += min(k1, k2);
        if (k1 > k2){
            cnt.erase(p2);
            cnt[p1] -= k2;
        }
        else {
            cnt.erase(p1);
            cnt[p2] -= k1;
            if (!cnt[p2]){
                cnt.erase(p2);
            }
        }
    }
    vector<int> f;
    for (auto [u, v]: cnt) f.push_back(v);
    sort(f.begin(), f.end());
    // f.back() -= f[0]
    while (f.size() > 1){
        out += f[0];
        f.back() -= f[0];
        f.erase(f.begin());
        if (!f.back()) f.pop_back();
        sort(f.begin(), f.end());
    }
    if (!f.empty()) out += f[0];
    return out;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2392 KB Output is correct
2 Correct 32 ms 2392 KB Output is correct
3 Correct 32 ms 2396 KB Output is correct
4 Correct 32 ms 2392 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 596 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 10 ms 1164 KB Output is correct
8 Correct 10 ms 1372 KB Output is correct
9 Correct 4 ms 1112 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 10 ms 1164 KB Output is correct
8 Correct 10 ms 1372 KB Output is correct
9 Correct 4 ms 1112 KB Output is correct
10 Correct 32 ms 2384 KB Output is correct
11 Correct 31 ms 2392 KB Output is correct
12 Execution timed out 1565 ms 2140 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 10 ms 1164 KB Output is correct
8 Correct 10 ms 1372 KB Output is correct
9 Correct 4 ms 1112 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 13 ms 1368 KB Output is correct
14 Correct 14 ms 1300 KB Output is correct
15 Correct 8 ms 1392 KB Output is correct

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2392 KB Output is correct
2 Correct 32 ms 2392 KB Output is correct
3 Correct 32 ms 2396 KB Output is correct
4 Correct 32 ms 2392 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 596 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1112 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 10 ms 1164 KB Output is correct
15 Correct 10 ms 1372 KB Output is correct
16 Correct 4 ms 1112 KB Output is correct
17 Correct 32 ms 2384 KB Output is correct
18 Correct 31 ms 2392 KB Output is correct
19 Execution timed out 1565 ms 2140 KB Time limit exceeded
20 Halted 0 ms 0 KB -