제출 #702773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702773		wenqi	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	147 ms	46596 KiB

shoes

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

using namespace std;
using ll = long long;

int N;
unordered_map<int, vector<int>> mp;

int bits[100069];

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

void update(int i)
{
    while (i < 100069)
    {
        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[s[i]].push_back(i);
    vector<pair<int, int>> ps;
    for (int i = 1; i <= N; i++)
    {
        auto &A = mp[-i];
        auto &B = mp[i];
        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;
}

컴파일 시 표준 에러 (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: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15