Submission #543836

#	Time	Username	Problem	Language	Result	Execution time	Memory
543836		Tien_Noob	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	8 ms	9716 KiB

shoes

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 2e5;
vector<int> id[N + 1][2];
struct FenwickTree
{
    int Tree[N + 1];
    void add(int pos, int val)
    {
        for (; pos <= N; pos += (pos & (-pos)))
        {
            Tree[pos] += val;
        }
    }
    int sum(int pos)
    {
        int ret = 0;
        for (; pos > 0; pos -= (pos & (-pos)))
        {
            ret += Tree[pos];
        }
        return ret;
    }
    int sum(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
} Tree;
long long count_swaps(vector<int> a)
{
    long long res = 0;
    int n = a.size();
    a.insert(a.begin(), 0);
    for (int i = 1; i <= n; ++ i)
    {
        int x = (a[i] < 0) ? 0 : 1;
        int b = abs(a[i]);
        if (!id[abs(a[i])][1 ^ x].empty())
        {
            int r = i + Tree.sum(i), l = id[b][1 ^ x].back() + Tree.sum(id[b][1 ^ x].back());
            res += r - l - (a[i] > 0);
            //cerr << r - l - (a[i] > 0) << '\n';
            Tree.add(i, -1);
            Tree.add(id[b][1 ^ x].back() + (a[i] > 0), 1);
            id[b][1 ^ x].pop_back();
        }
        else
        {
            id[b][x].push_back(i);
        }
    }
    return res;
}
/*void read()
{
    cout << count_swaps({-2, 2, 2, -2, -2, 2});
}
void solve()
{

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}*/

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