Submission #823199

#	Time	Username	Problem	Language	Result	Execution time	Memory
823199		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	50 ms	16428 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>

using namespace std;

struct fenwick {
    vector<int> t;
    fenwick(int N) : t(N + 1, 0) {}

    void upd(int x, int g) {
        while (x < t.size()) {
            t[x] += g;
            x += x & -x;
        }
    }

    int get(int x) {
        int res = 0;
        while (x > 0) {
            res += t[x];
            x -= x & -x;
        }
        return res;
    }
};

long long count_swaps(std::vector<int> s) {
    vector<vector<int>> A(s.size() / 2);
    vector<vector<int>> B(s.size() / 2);
    for (int i = 0; i < s.size(); i++) {
        int x = abs(s[i]) - 1;
        if (s[i] < 0) {
            A[x].push_back(i);
        } else {
            B[x].push_back(i);
        }
    }
    for (int i = 0; i < s.size() / 2; i++) {
        reverse(A[i].begin(), A[i].end());
        reverse(B[i].begin(), B[i].end());
    }
    vector<int> used(s.size(), 0);
    vector<int> p(s.size());
    for (int i = 0, j = 1; i < s.size(); i++) {
        if (used[i]) {
            continue;
        }
        int x = abs(s[i]) - 1;
        p[A[x].back()] = j++;
        p[B[x].back()] = j++;
        used[A[x].back()] = used[B[x].back()] = true;
        A[x].pop_back();
        B[x].pop_back();
    }

    long long res = 0;
    fenwick tree(s.size() + 1);
    for (int i = s.size() - 1; i >= 0; i--) {
        res += tree.get(p[i]);
        tree.upd(p[i], 1);
    }

    return res;
}

Compilation message (stderr)

shoes.cpp: In member function 'void fenwick::upd(int, int)':
shoes.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         while (x < t.size()) {
      |                ~~^~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
shoes.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < s.size() / 2; i++) {
      |                     ~~^~~~~~~~~~~~~~
shoes.cpp:45:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0, j = 1; i < s.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