Submission #673662

#	Time	Username	Problem	Language	Result	Execution time	Memory
673662		stanislavpolyn	The Collection Game (BOI21_swaps)	C++17	25 / 100	111 ms	516 KiB

swaps

#include <bits/stdc++.h>
 
#include "swaps.h"
 
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
 
#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
 
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key
 
template <typename T>
bool umn(T& a, T b) { return (a > b ? (a = b, 1) : 0); }
template <typename T>
bool umx(T& a, T b) { return (a < b ? (a = b, 1) : 0); }
 
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;
 
const int N = 505;
 
int t[4 * N];
int szT;
 
void solve(int N, int V) {
    szT = 1;
    while (szT < N) szT *= 2;
 
    ve<bool> mark(N + 1);
    ve<int> res;
 
    while (sz(res) < N) {
        fill(t, t + 2 * szT, 0);
        ve<int> v;
        fr (i, szT, szT * 2 - 1) {
            if (i - szT + 1 <= N && !mark[i - szT + 1]) {
                t[i] = i - szT + 1;
            } else {
                t[i] = 0;
            }
            if (!sz(v) || v.back() != i / 2) {
                v.pb(i / 2);
            }
        }
 
        while (1) {
            fe (cur, v) {
                // cur * 2, cur * 2 + 1
                if (t[cur * 2] == 0) t[cur] = t[cur * 2 + 1];
                else if (t[cur * 2 + 1] == 0) t[cur] = t[cur * 2];
                else {
                    schedule(t[cur * 2], t[cur * 2 + 1]);
                }
            }
            ve<int> answers = visit();
 
            int ptr = 0;
            fe (cur, v) {
                if (t[cur * 2] && t[cur * 2 + 1]) {
                    if (answers[ptr]) {
                        t[cur] = t[cur * 2];
                    } else {
                        t[cur] = t[cur * 2 + 1];
                    }
                    ptr++;
                }
            }
            if (sz(v) == 1) {
                break;
            }
            ve<int> newV;
            fe (cur, v) {
                if (!sz(newV) || newV.back() != cur / 2) {
                    newV.pb(cur / 2);
                }
            }
            v = newV;
        }
        res.pb(t[1]);
        mark[t[1]] = 1;
        {
            int v = t[1] + szT - 1;
            while (1) {
                t[v] = 0;
 
                if (v == 1) break;
                v /= 2;
            }
        }
    }
 
    answer(res);
}

• 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