oj.uz

Submission #405815

# Submission time Handle Problem Language Result Execution time Memory
405815 2021-05-16T23:18:05 Z 534351 The Collection Game (BOI21_swaps) C++17
25 / 100
 104 ms 472 KB 
//
// --- 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 11 ms 296 KB Correct
3 Correct 33 ms 308 KB Correct
4 Correct 77 ms 444 KB Correct
5 Correct 71 ms 464 KB Correct
6 Correct 79 ms 304 KB Correct
7 Correct 94 ms 428 KB Correct
8 Correct 84 ms 328 KB Correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 9 ms 200 KB Correct
3 Correct 34 ms 304 KB Correct
4 Correct 96 ms 312 KB Correct
5 Correct 85 ms 352 KB Correct
6 Correct 97 ms 304 KB Correct
7 Correct 93 ms 464 KB Correct
8 Correct 104 ms 308 KB Correct
9 Runtime error 28 ms 300 KB Execution killed with signal 13
10 Halted 0 ms 0 KB -

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 8 ms 200 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 8 ms 200 KB Correct
3 Correct 1 ms 200 KB Correct
4 Correct 7 ms 200 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 9 ms 200 KB Correct
3 Correct 35 ms 200 KB Correct
4 Correct 100 ms 304 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 9 ms 200 KB Correct
3 Correct 35 ms 200 KB Correct
4 Correct 100 ms 304 KB Correct
5 Correct 1 ms 200 KB Correct
6 Correct 10 ms 200 KB Correct
7 Correct 35 ms 300 KB Correct
8 Correct 95 ms 312 KB Correct
9 Correct 88 ms 324 KB Correct
10 Correct 91 ms 472 KB Correct
11 Correct 95 ms 300 KB Correct
12 Correct 84 ms 340 KB Correct
13 Correct 1 ms 200 KB Correct
14 Correct 11 ms 200 KB Correct
15 Correct 28 ms 200 KB Correct
16 Correct 97 ms 328 KB Correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 9 ms 200 KB Correct
3 Correct 32 ms 300 KB Correct
4 Correct 84 ms 316 KB Correct
5 Runtime error 17 ms 304 KB Execution killed with signal 13

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 9 ms 200 KB Correct
3 Correct 32 ms 300 KB Correct
4 Correct 84 ms 316 KB Correct
5 Runtime error 17 ms 304 KB Execution killed with signal 13

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 8 ms 200 KB Correct
3 Correct 29 ms 200 KB Correct
4 Correct 89 ms 300 KB Correct
5 Runtime error 19 ms 288 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 8 ms 200 KB Correct
3 Correct 29 ms 200 KB Correct
4 Correct 89 ms 300 KB Correct
5 Runtime error 19 ms 288 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 8 ms 200 KB Correct
3 Correct 31 ms 312 KB Correct
4 Correct 90 ms 308 KB Correct
5 Runtime error 16 ms 288 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 8 ms 200 KB Correct
3 Correct 31 ms 312 KB Correct
4 Correct 90 ms 308 KB Correct
5 Runtime error 16 ms 288 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -