Submission #673662

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
673662	2022-12-21T15:24:42 Z	stanislavpolyn	The Collection Game (BOI21_swaps)	C++17	25 / 100	111 ms	516 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	296 KB	Correct
2	Correct	5 ms	348 KB	Correct
3	Correct	30 ms	296 KB	Correct
4	Correct	79 ms	328 KB	Correct
5	Correct	82 ms	328 KB	Correct
6	Correct	86 ms	324 KB	Correct
7	Correct	83 ms	324 KB	Correct
8	Correct	75 ms	316 KB	Correct

Subtask #2
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	9 ms	208 KB	Correct
3	Correct	23 ms	292 KB	Correct
4	Correct	102 ms	328 KB	Correct
5	Correct	80 ms	428 KB	Correct
6	Correct	70 ms	332 KB	Correct
7	Correct	83 ms	324 KB	Correct
8	Correct	76 ms	320 KB	Correct
9	Runtime error	26 ms	444 KB	Execution killed with signal 11
10	Halted	0 ms	0 KB	-

Subtask #3
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	9 ms	208 KB	Correct

Subtask #4
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	9 ms	208 KB	Correct
3	Correct	0 ms	208 KB	Correct
4	Correct	7 ms	208 KB	Correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	7 ms	208 KB	Correct
3	Correct	26 ms	292 KB	Correct
4	Correct	98 ms	488 KB	Correct

Subtask #6
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	7 ms	208 KB	Correct
3	Correct	26 ms	292 KB	Correct
4	Correct	98 ms	488 KB	Correct
5	Correct	1 ms	208 KB	Correct
6	Correct	9 ms	208 KB	Correct
7	Correct	23 ms	304 KB	Correct
8	Correct	73 ms	448 KB	Correct
9	Correct	84 ms	316 KB	Correct
10	Correct	78 ms	320 KB	Correct
11	Correct	78 ms	324 KB	Correct
12	Correct	54 ms	324 KB	Correct
13	Correct	1 ms	208 KB	Correct
14	Correct	10 ms	208 KB	Correct
15	Correct	31 ms	208 KB	Correct
16	Correct	73 ms	348 KB	Correct

Subtask #7
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	7 ms	208 KB	Correct
3	Correct	34 ms	208 KB	Correct
4	Correct	88 ms	308 KB	Correct
5	Runtime error	14 ms	432 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #8
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	7 ms	208 KB	Correct
3	Correct	34 ms	208 KB	Correct
4	Correct	88 ms	308 KB	Correct
5	Runtime error	14 ms	432 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #9
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	208 KB	Correct
2	Correct	9 ms	300 KB	Correct
3	Correct	28 ms	296 KB	Correct
4	Correct	80 ms	324 KB	Correct
5	Runtime error	12 ms	404 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #10
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	208 KB	Correct
2	Correct	9 ms	300 KB	Correct
3	Correct	28 ms	296 KB	Correct
4	Correct	80 ms	324 KB	Correct
5	Runtime error	12 ms	404 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #11
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	8 ms	208 KB	Correct
3	Correct	23 ms	208 KB	Correct
4	Correct	111 ms	440 KB	Correct
5	Runtime error	14 ms	516 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #12
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	8 ms	208 KB	Correct
3	Correct	23 ms	208 KB	Correct
4	Correct	111 ms	440 KB	Correct
5	Runtime error	14 ms	516 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Submission #673662

Compilation message