Submission #318459

#	Time	Username	Problem	Language	Result	Execution time	Memory
318459		joylintp	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	188 ms	141292 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;

int n;
long long BIT[200001];
vector<queue<int>> ls, rs;

void mod(int p, int x)
{
    while (p <= n)
        BIT[p] += x, p += p & -p;
}

int qry(int p)
{
    int ret = 0;
    while (p)
        ret += BIT[p], p -= p & -p;
    return ret;
}

long long count_swaps(vector<int> ss)
{
    n = ss.size();
	vector<int> s = {0};
	for (int i : ss)
        s.push_back(i);

    ls.resize(n / 2 + 1), rs.resize(n / 2 + 1);
    for (int i = 1; i <= n; i++)
        if (s[i] < 0)
            ls[-s[i]].push(i);
        else
            rs[s[i]].push(i);

    for (int i = 1; i <= n; i++)
        mod(i, 1);

    long long ans = 0;
    for (int i = 1; i <= n; i++)
        if (qry(i))
            if (s[i] < 0)
            {
                int lpos = i, rpos = rs[-s[i]].front();
                ls[-s[i]].pop(), rs[-s[i]].pop();

                ans += qry(rpos - 1) - qry(lpos);
                mod(lpos, -1), mod(rpos, -1);
            }
            else
            {
                int lpos = ls[s[i]].front(), rpos = i;
                ls[s[i]].pop(), rs[s[i]].pop();

                ans += qry(lpos - 1) - qry(rpos - 1);
                mod(lpos, -1), mod(rpos, -1);
            }

    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:42:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   42 |         if (qry(i))
      |            ^

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