Submission #443121

#	Time	Username	Problem	Language	Result	Execution time	Memory
443121		ak2006	Mutating DNA (IOI21_dna)	C++17	0 / 100	128 ms	2356 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
string a,b;
void init(string A, string B) {
    a = A;
    b = B;
}
struct BIT
{
    int n;
    vl bit;
    BIT(int _n)
    {
        n = _n;
        bit.assign(n + 1,0);
    }
    void update(int i,ll inc)
    {
        for (;i>0;i-=i&(-i))bit[i] += inc;
    }
    ll sum(int i)
    {
        ll ret = 0;
        for (;i<=n;i+=i&(-i))ret += bit[i];
        return ret;
    }
};
ll cnt_Inversions(vi&p)
{
    int n = (int)p.size();
    BIT ds(n);
    ll ret = 0;
    for (int i = 1;i<=n;i++){
        int val = p[i - 1];
        ret += ds.sum(val + 1);
        ds.update(val + 1,1);
    }
    return ret;
}
ll get_ans(string s1,string s2)
{
    int n = (int)s1.size();
    vvi pos(26);
    vvi rpos(26);
    for (int i = 0;i<n;i++)
        pos[s1[i] - 'A'].pb(i);
    for (int i = 0;i<n;i++)
        rpos[s2[i] - 'A'].pb(i);
    vi ppos(26);
    vi p(n);
    for (int i = 0;i<n;i++){
        char cur = s1[i];
        p[i] = rpos[cur - 'A'][ppos[cur - 'A']];
        ppos[cur - 'A']++;
    }
    return cnt_Inversions(p);
 
}
int get_distance(int x, int y) {
    map<char,vi>pos1,pos2;

    for (int i = x;i<=y;i++){
        pos1[a[i]].pb(i);
        pos2[b[i]].pb(i);
    }

    if (pos1['A'].size() != pos2['A'].size() or pos1['T'].size() != pos2['T'].size()
    or pos1['C'].size() != pos2['C'].size())return -1;
    
    return get_ans(a.substr(x,y - x + 1),b.substr(x,y - x + 1));
}

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