Submission #405815

#	Time	Username	Problem	Language	Result	Execution time	Memory
405815		534351	The Collection Game (BOI21_swaps)	C++17	25 / 100	104 ms	472 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 <bits/stdc++.h>

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

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, Q;
vpi cand;
vi ans;

vi work()
{
    for (pii p : cand)
    {
        schedule(p.fi + 1, p.se + 1);
    }
    cand.clear();
    return visit();
}
int find_winner(vi v)
{
    if (SZ(v) == 1)
    {
        return v[0];
    }
    vi lol;
    for (int i = 1; i < SZ(v); i += 2)
    {
        cand.PB({v[i - 1], v[i]});
    }
    auto res = work();
    FOR(i, 0, SZ(res))
    {
        lol.PB(v[2 * i + 1 - res[i]]);
    }
    if (SZ(v) & 1) lol.PB(v.back());
    return find_winner(lol);
}
void solve(int n, int q)
{
    N = n; Q = q;
    //try to figure out which one allows more?
    vi nums(N); iota(ALL(nums), 0);
    FOR(i, 0, N)
    {
        int x = find_winner(nums);
        ans.PB(x);
        nums.erase(find(ALL(nums), x));
    }
    for (int &x : ans)
    {
        x++;
    }
    answer(ans);
    return;
    // TODO implement this function
    // schedule(1, 2);
    // std::vector<int> v = visit();
    // if (v[0] == 1)
    //     answer({1, 2, 3, 4});
    // else
    //     answer({2, 1, 3, 4});
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 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