Submission #702776

#	Time	Username	Problem	Language	Result	Execution time	Memory
702776		wenqi	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	83 ms	15296 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int N;
vector<int> mp[100069][2];

int bits[200069];

int query(int i)
{
    int sum = 0;
    while (i)
    {
        sum += bits[i];
        i -= i & -i;
    }
    return sum;
}

void update(int i)
{
    while (i <= 2 * N)
    {
        bits[i]++;
        i += i & -i;
    }
}

long long count_swaps(vector<int> s)
{
    N = s.size() / 2;
    for (int i = 0; i < 2 * N; i++)
        mp[abs(s[i])][s[i] > 0].push_back(i);
    vector<pair<int, int>> ps;
    for (int i = 1; i <= N; i++)
    {
        auto &A = mp[i][0];
        auto &B = mp[i][1];
        for (int j = 0; j < A.size(); j++)
            ps.push_back({A[j], B[j]});
    }
    sort(ps.begin(), ps.end(), [] (pair<int, int> a, pair<int, int> b) {
        int x = a.first + a.second;// + (a.second > a.first);
        int y = b.first + b.second;// + (b.second > b.first);
        return x < y;
    });
    vector<int> R(2 * N);
    int c = 1;
    for (auto [a, b] : ps)
    {
        R[a] = c++;
        R[b] = c++;
    }
    ll invs = 0;
    for (int i = 0; i < 2 * N; i++)
    {
        invs += i - query(R[i]);
        update(R[i]);
    }
    return invs;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int j = 0; j < A.size(); j++)
      |                         ~~^~~~~~~~~~

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