Submission #671251

#	Time	Username	Problem	Language	Result	Execution time	Memory
671251		pls33	Mutating DNA (IOI21_dna)	C++17	35 / 100	36 ms	6688 KiB

dna

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "dna.h"
using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
#pragma endregion

vvi32 count_a, count_b;
vi32 diff;

int query(int i, int j, vi32 &prefix)
{
    int sum = prefix[j];
    if (i)
    {
        sum -= prefix[i - 1];
    }

    return sum;
}

void init(std::string a, std::string b)
{
    count_a = vvi32(3, vi32(a.size()));
    count_b = count_a;

    diff = vi32(a.size());

    for (int i = 0; i < (int)a.size(); i++)
    {
        if (a[i] != b[i])
        {
            diff[i]++;
        }

        a[i] = clamp(a[i], 'A', 'C') - 'A';
        b[i] = clamp(b[i], 'A', 'C') - 'A';

        count_a[a[i]][i]++;
        count_b[b[i]][i]++;

        if (i)
        {
            diff[i] += diff[i - 1];
            for (int j = 0; j < 3; j++)
            {
                count_a[j][i] += count_a[j][i - 1];
                count_b[j][i] += count_b[j][i - 1];
            }
        }
    }
}

int get_distance(int x, int y)
{
    bool ok = true;
    for (int i = 0; i < 3; i++)
    {
        if (query(x, y, count_a[i]) != query(x, y, count_b[i]))
        {
            ok = false;
            break;
        }
    }

    if (!ok)
    {
        return -1;
    }

    int count = query(x, y, diff);
    return count / 2 + int(bool(count % 2));
}

Compilation message (stderr)

dna.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
dna.cpp:31: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   31 | #pragma endregion
      |

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