Submission #1092908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092908		Pannda	Meetings (JOI19_meetings)	C++17	100 / 100	654 ms	1100 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>
using namespace std;

void Solve(int n) {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    auto query = [&](int u, int v, int w) -> int {
        return Query(u, v, w);
    };

    auto bridge = [&](int u, int v) -> void {
        if (u > v) swap(u, v);
        Bridge(u, v);
    };

    auto work = [&](auto self, vector<int> dom) -> void {
        if (dom.size() == 1) return;
        shuffle(dom.begin(), dom.end(), rng);
        int r0 = dom.back(); dom.pop_back();
        int r1 = dom.back(); dom.pop_back();

        vector<int> v0 = {r0};
        vector<int> v1 = {r1};
        map<int, vector<int>> v;

        for (int u : dom) {
            int get = Query(r0, r1, u);
            if (get == r0) {
                v0.push_back(u);
            } else if (get == r1) {
                v1.push_back(u);
            } else {
                v[get].push_back(u);
            }
        }

        vector<int> perm;
        self(self, v0);
        self(self, v1);
        for (auto [r, d] : v) {
            self(self, d);
            perm.push_back(r);
        }

        sort(perm.begin(), perm.end(), [&](int u, int v) {
            return Query(u, v, r0) == u;
        });
        perm.insert(perm.begin(), r0);
        perm.push_back(r1);
        for (int i = 0; i + 1 < perm.size(); i++) {
            bridge(perm[i], perm[i + 1]);
        }

    };

    work(work, [&]() -> vector<int> {
        vector<int> dom(n);
        iota(dom.begin(), dom.end(), 0);
        return dom;
    }());
}

Compilation message (stderr)

meetings.cpp: In lambda function:
meetings.cpp:52:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (int i = 0; i + 1 < perm.size(); i++) {
      |                         ~~~~~~^~~~~~~~~~~~~
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:9:10: warning: variable 'query' set but not used [-Wunused-but-set-variable]
    9 |     auto query = [&](int u, int v, int w) -> int {
      |          ^~~~~
meetings.cpp: In instantiation of 'Solve(int)::<lambda(auto:23, std::vector<int>)> [with auto:23 = Solve(int)::<lambda(auto:23, std::vector<int>)>]':
meetings.cpp:62:8:   required from here
meetings.cpp:52:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (int i = 0; i + 1 < perm.size(); i++) {
      |                         ~~~~~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71