oj.uz

Submission #405839

# Submission time Handle Problem Language Result Execution time Memory
405839 2021-05-16T23:41:28 Z 534351 The Collection Game (BOI21_swaps) C++17
25 / 100
 111 ms 580 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()
{
    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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 8 ms 200 KB Correct
3 Correct 37 ms 312 KB Correct
4 Correct 89 ms 348 KB Correct
5 Correct 105 ms 324 KB Correct
6 Correct 86 ms 340 KB Correct
7 Correct 84 ms 336 KB Correct
8 Correct 99 ms 308 KB Correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 7 ms 296 KB Correct
3 Correct 37 ms 200 KB Correct
4 Correct 111 ms 336 KB Correct
5 Correct 91 ms 436 KB Correct
6 Correct 110 ms 344 KB Correct
7 Correct 85 ms 324 KB Correct
8 Correct 79 ms 544 KB Correct
9 Incorrect 4 ms 300 KB Not correct
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 9 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 9 ms 200 KB Correct
3 Correct 1 ms 200 KB Correct
4 Correct 12 ms 292 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 7 ms 200 KB Correct
3 Correct 25 ms 308 KB Correct
4 Correct 97 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 7 ms 200 KB Correct
3 Correct 25 ms 308 KB Correct
4 Correct 97 ms 304 KB Correct
5 Correct 1 ms 200 KB Correct
6 Correct 10 ms 292 KB Correct
7 Correct 37 ms 312 KB Correct
8 Correct 103 ms 344 KB Correct
9 Correct 87 ms 328 KB Correct
10 Correct 66 ms 356 KB Correct
11 Correct 98 ms 432 KB Correct
12 Correct 79 ms 340 KB Correct
13 Correct 1 ms 200 KB Correct
14 Correct 8 ms 200 KB Correct
15 Correct 27 ms 308 KB Correct
16 Correct 68 ms 580 KB Correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 10 ms 200 KB Correct
3 Correct 37 ms 308 KB Correct
4 Correct 90 ms 300 KB Correct
5 Incorrect 3 ms 260 KB Not correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 10 ms 200 KB Correct
3 Correct 37 ms 308 KB Correct
4 Correct 90 ms 300 KB Correct
5 Incorrect 3 ms 260 KB Not correct

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 7 ms 200 KB Correct
3 Correct 21 ms 352 KB Correct
4 Correct 99 ms 332 KB Correct
5 Incorrect 3 ms 296 KB Not correct
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 7 ms 200 KB Correct
3 Correct 21 ms 352 KB Correct
4 Correct 99 ms 332 KB Correct
5 Incorrect 3 ms 296 KB Not correct
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 10 ms 292 KB Correct
3 Correct 38 ms 292 KB Correct
4 Correct 90 ms 468 KB Correct
5 Incorrect 4 ms 300 KB Not correct
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 10 ms 292 KB Correct
3 Correct 38 ms 292 KB Correct
4 Correct 90 ms 468 KB Correct
5 Incorrect 4 ms 300 KB Not correct
6 Halted 0 ms 0 KB -