Submission #941434

#	Time	Username	Problem	Language	Result	Execution time	Memory
941434		Programmer123	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	636 ms	165080 KiB

shoes

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

struct node {
    int min, max;
    node *left, *right;
    int value;

    node(int l, int r) {
        min = l;
        max = r;
        if (r == l + 1) {
            left = right = nullptr;
        } else {
            left = new node(l, (l + r) / 2);
            right = new node((l + r) / 2, r);
        }
        value = max - min;
    }

    void erase(int x) {
        if (x < min || x >= max) return;
        value--;
        if (x == min && x + 1 == max) return;
        left->erase(x);
        right->erase(x);
    }

    int query(int l, int r) const {
        l = std::max(l, min);
        r = std::min(r, max);
        if (l >= r) return 0;
        if (l >= max || r <= min) return 0;
        if (l == min && r == max) return value;
        return left->query(l, r) + right->query(l, r);
    }
};

bool valid(std::vector<int> s) {
    for (int i = 0; i < s.size() / 2; ++i) {
        if (s[2 * i] > 0) return false;
        if (s[2 * i + 1] < 0) return false;
        if (s[2 * i] != -s[2 * i + 1]) return false;
    }
    return true;
}

std::vector<std::vector<int>> swaps(std::vector<int> s) {
    std::vector<std::vector<int>> result;
    for (int i = 0; i < s.size() - 1; ++i) {
        auto x = s;
        std::swap(x[i], x[i + 1]);
        result.push_back(x);
    }
    return result;
}

long long bruteforce(std::vector<int> s) {
    if (valid(s)) return 0;
    std::queue<std::pair<int, std::vector<int>>> bfs;
    std::set<std::vector<int>> seen;
    bfs.emplace(0, s);
    while (!bfs.empty()) {
        auto [d, n] = bfs.front();
        bfs.pop();
        for (const auto &x: swaps(n)) {
            if (seen.count(x)) continue;
            if (valid(x)) return d + 1;
            seen.insert(x);
            bfs.emplace(d + 1, x);
        }
    }
    return -1;
}

long long count_swaps(std::vector<int> s) {
#ifdef LOCAL
    long long slow = bruteforce(s);
    std::cout << "Slow solution is " << slow << std::endl;
#endif
    int N = s.size() / 2;
    node tree(0, 2 * N);
    long long ans = 0;
    auto moveLeft = [&](int idx) {
        ans += tree.query(0, idx);
        tree.erase(idx);
    };
    std::map<int, std::queue<int>> rights, lefts;
    for (int i = 0; i < 2 * N; ++i) {
        if (s[i] > 0) {
            rights[s[i]].push(i);
        } else {
            lefts[-s[i]].push(i);
        }
    }
    for (int i = 0; i < 2 * N; ++i) {
        if (tree.query(i, i + 1) == 0) continue;
        if (s[i] < 0) {
            assert(!rights[-s[i]].empty());
            int x = rights[-s[i]].front();
            rights[-s[i]].pop();
            assert(lefts[-s[i]].front() == i);
            lefts[-s[i]].pop();
            moveLeft(i);
            moveLeft(x);
        } else {
            assert(rights[s[i]].front() == i);
            rights[s[i]].pop();
            moveLeft(i);
            int x = lefts[s[i]].front();
            lefts[s[i]].pop();
            moveLeft(x);
            ans++;
        }
    }
    assert(tree.value == 0);
    for (auto [a, b]: rights) {
        assert(b.empty());
    }
#ifdef LOCAL
    std::cout << "Fast solution is " << ans << std::endl;
    assert(slow == ans);
#endif
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'bool valid(std::vector<int>)':
shoes.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < s.size() / 2; ++i) {
      |                     ~~^~~~~~~~~~~~~~
shoes.cpp: In function 'std::vector<std::vector<int> > swaps(std::vector<int>)':
shoes.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i < s.size() - 1; ++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