Submission #732229

#	Time	Username	Problem	Language	Result	Execution time	Memory
732229		Stickfish	The Collection Game (BOI21_swaps)	C++17	35 / 100	35 ms	444 KiB

swaps

//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
//     swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//
#include "swaps.h"
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;

void get_stree_nodes(int d, int l, int r, vector<vector<pair<int, int>>>& ans) {
    if (r - l == 1)
        return;
    if (d >= ans.size())
        ans.push_back({});
    ans[d].push_back({l, r});
    int m = (l + r) / 2;
    get_stree_nodes(d + 1, l, m, ans);
    get_stree_nodes(d + 1, m, r, ans);
}

void solve(int N, int V) {
    vector<int> v(N);
    for (int i = 0; i < N; ++i)
        v[i] = i + 1;
    vector<vector<pair<int, int>>> nds;
    get_stree_nodes(0, 0, N, nds);
    for (int d = nds.size() - 1; d >= 0; --d) {
        vector<pair<pair<int, int>, pair<int, int>>> sgs;
        for (auto [l, r] : nds[d]) {
            int m = (l + r) / 2;
            sgs.push_back({{l, m}, {m, r}});
        }
        // cout << endl;
        for (auto& [s1, s2] : sgs) {
            if (s2.second - s2.first != s1.second - s1.first) {
                assert(s2.second - s2.first - 1 == s1.second - s1.first);
                --s2.second;
                // cout << "(" << s1.first << ' ' << s1.second << ' ' << s2.first << ' ' << s2.second << ") ";
            }
        }
        // cout << endl;
        bool cont = true;
        while (cont) {
            cont = false;
            for (auto [s1, s2] : sgs) {
                if (s2.second <= s2.first)
                    continue;
                cont = true;
                for (int i = 0; i < s2.second - s2.first; ++i)
                    schedule(v[s1.first + i], v[s2.first + i]);
            }
            if (!cont)
                break;
            vector<int> vis = visit();
            int visi = 0;
            for (auto& [s1, s2] : sgs) {
                if (s2.second <= s1.first)
                    continue;
                for (int i = 0; i < s2.second - s2.first; ++i) {
                    if (!vis[visi++])
                        swap(v[s1.first + i], v[s2.first + i]);
                }
                ++s1.first;
                --s2.second;
            }
        }
        vector<pair<int, int>> leftover;
        for (auto& p : nds[d]) {
            if ((p.second - p.first) % 2) {
                leftover.push_back({p.first, p.second - 1});
            }
            else
                leftover.push_back({-1, -1});
        }
        while (true) {
            bool isleft = false;
            for (auto x : leftover) {
                isleft |= x.first < x.second;
            }
            if (!isleft)
                break;
            for (size_t i = 0; i < leftover.size(); ++i) {
                if (leftover[i].first >= leftover[i].second)
                    continue;
                schedule(v[leftover[i].first], v[leftover[i].second]);
            }
            vector<int> vis = visit();
            int visi = 0;
            for (size_t i = 0; i < leftover.size(); ++i) {
                if (leftover[i].first >= leftover[i].second)
                    continue;
                if (!vis[visi++])
                    swap(v[leftover[i].first], v[leftover[i].second]);
                ++leftover[i].first;
            }
        }
    }
    answer(v);
}

Compilation message (stderr)

swaps.cpp: In function 'void get_stree_nodes(int, int, int, std::vector<std::vector<std::pair<int, int> > >&)':
swaps.cpp:19:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     if (d >= ans.size())
      |         ~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 9 / 9
• Subtask 6: 6 / 6
• Subtask 7: 0 / 9
• Subtask 8: 0 / 6
• Subtask 9: 0 / 21
• Subtask 10: 0 / 14
• Subtask 11: 0 / 9
• Subtask 12: 0 / 6