oj.uz

Submission #443121

# Submission time Handle Problem Language Result Execution time Memory
443121 2021-07-09T18:28:39 Z ak2006 Mutating DNA (IOI21_dna) C++17
0 / 100
 128 ms 2356 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 2356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 2 ms 972 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 2 ms 972 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 2 ms 972 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 2356 KB Output isn't correct
2 Halted 0 ms 0 KB -