Submission #1195580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195580		nekolie	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	77 ms	14664 KiB

shoes

// When she's prettier than any DP you've ever seen...
#include <bits/stdc++.h>
using namespace std;

const int baza = (1<<18); int d[2*baza];
int pierwszy() {
    int v = 1;
    while (v < baza)
        v = ((d[2*v] > 0) ? 2*v : 2*v+1);
    return v-baza;
}
void akt(int i) {
    i = (i+baza)/2;
    while (i > 0)
        d[i] = d[2*i]+d[2*i+1], i /= 2;
}
int suma(int l, int r) {
    int wynik = 0; l += baza-1, r += baza+1;
    while (l/2 != r/2) {
        if (l%2 == 0)
            wynik += d[l+1];
        if (r%2 == 1)
            wynik += d[r-1];
        l /= 2, r /= 2;
    }
    return wynik;
}
long long count_swaps(vector<int> S)
{
    int n = S.size()/2;
    vector<int> ind[n+1][2];
    for (int i = 2*n-1; i >= 0; i--) {
        d[i+baza] = 1;
        if (S[i] < 0)
            ind[-S[i]][0].push_back(i);
        else
            ind[S[i]][1].push_back(i);
    }
    for (int i = baza-1; i > 0; i--)
        d[i] = d[2*i]+d[2*i+1];
    long long odp = 0;
    while (d[1] > 0) {
        int x = pierwszy(), y;
        if (S[x] > 0)
            y = ind[S[x]][0].back(), odp++;
        else
            y = ind[-S[x]][1].back();
        ind[abs(S[x])][0].pop_back(), ind[abs(S[x])][1].pop_back();
        d[x+baza] = d[y+baza] = 0, akt(x), akt(y), odp += suma(x,y);
    }
    return odp;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15