제출 #289829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
289829		IgorI	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	291 ms	13432 KiB

shoes

#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <cstdlib>
#include <iostream>
#include <map>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (int (i) = 0; (i) < (n); (i)++)

const int N = 540400;

int fenw[N];

void add(int pos)
{
    while (pos < N)
    {
        fenw[pos]++;
        pos = (pos | (pos + 1));
    }
}

int get(int pos)
{
    int res = 0;
    while (pos >= 0)
    {
        res += fenw[pos];
        pos = (pos & (pos + 1)) - 1;
    }
    return res;
}

long long count_swaps(vector<int> a)
{
    int n = a.size() / 2;
    long long ans = 0;
    set<pair<int, int> > s;
    for (int i = 0; i < a.size(); i++)
    {
        s.insert({a[i], i});
    }
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        while (get(j) - get(j - 1) != 0) j++;
        pair<int, int> x = {a[j], j};
        s.erase(x);
        auto it2 = s.lower_bound({-x.first, -1});
        pair<int, int> y = *it2;
        //cout << x.first << " " << x.second << "->" << y.first << " " << y.second << "\n";
        s.erase(y);
        int real_pos = y.second + get(a.size()) - get(y.second);
        add(y.second);
        add(x.second);
        ans += abs(real_pos - (2 * i + 1));
        if (x.first > 0) ans++;
    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < a.size(); 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