Submission #405839

#	Time	Username	Problem	Language	Result	Execution time	Memory
405839		534351	The Collection Game (BOI21_swaps)	C++17	25 / 100	111 ms	580 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()
{
    if (cand.empty()) return vector<int>();
    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?
    if (Q >= 5000)
    {
        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);
    }
    //always move (i...j)
    //????
    for (int i = (1 << 31 - __builtin_clz(N)); i; i >>= 1)
    {
        FOR(j, 0, N - i)
        {
            if (j % (2 * i) < i)
            {
                cand.PB({j, j + i});
            }
        }
        work();
        FOR(j, 0, N - i)
        {
            if (j % (2 * i) >= i)
            {
                cand.PB({j, j + i});
            }
        }
        work();
        FOR(j, 0, N - i)
        {
            if (j % (2 * i) < i)
            {
                cand.PB({j, j + i});
            }
        }
        work();
    }
    ans.resize(N);
    iota(ALL(ans), 1);
    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});
}

Compilation message (stderr)

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:101:27: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  101 |     for (int i = (1 << 31 - __builtin_clz(N)); i; i >>= 1)
      |                        ~~~^~~~~~~~~~~~~~~~~~

• 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