oj.uz

Submission #1050182

# Submission time Handle Problem Language Result Execution time Memory
1050182 2024-08-09T07:53:10 Z shiomusubi496 The Collection Game (BOI21_swaps) C++17
15 / 100
 32 ms 1440 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 "swaps.h"
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

mt19937 mt(random_device{}());

void solve(int N, int V) {
    vector<vector<int>> g(N);
    rep2 (k, 1, N) {
        rep (i, N) {
            if (i / k % 2 == 1) continue;
            if (i + k < N) schedule(i + 1, i + k + 1);
        }
        auto res = visit();
        int cnt = 0;
        rep (i, N) {
            if (cnt == res.size()) break;
            if (i / k % 2 == 1) continue;
            if (res[cnt++]) g[i].push_back(i + k);
            else g[i + k].push_back(i);
        }
        rep (i, N) {
            if (i / k % 2 == 0) continue;
            if (i + k < N) schedule(i + 1, i + k + 1);
        }
        res = visit();
        cnt = 0;
        rep (i, N) {
            if (cnt == res.size()) break;
            if (i / k % 2 == 0) continue;
            if (res[cnt++]) g[i].push_back(i + k);
            else g[i + k].push_back(i);
        }
    }
    vector<int> tps;
    {
        vector<bool> used(N);
        vector<int> ord;
        auto dfs = [&](auto&& self, int v) -> void {
            used[v] = true;
            for (int u : g[v]) if (!used[u]) self(self, u);
            ord.push_back(v);
        };
        rep (v, N) if (!used[v]) dfs(dfs, v);
        reverse(all(ord));
        tps = ord;
    }
    rep (i, N) ++tps[i];
    answer(tps);
}

Compilation message

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             if (cnt == res.size()) break;
      |                 ~~~~^~~~~~~~~~~~~
swaps.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if (cnt == res.size()) break;
      |                 ~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 7 ms 656 KB Correct
4 Correct 25 ms 1184 KB Correct
5 Correct 23 ms 1168 KB Correct
6 Correct 26 ms 1124 KB Correct
7 Correct 24 ms 1252 KB Correct
8 Correct 32 ms 1440 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 3 ms 344 KB Correct
3 Correct 7 ms 664 KB Correct
4 Correct 27 ms 1360 KB Correct
5 Correct 23 ms 1072 KB Correct
6 Correct 28 ms 1144 KB Correct
7 Correct 24 ms 1292 KB Correct
8 Correct 26 ms 1096 KB Correct
9 Correct 23 ms 1132 KB Correct
10 Correct 23 ms 1220 KB Correct
11 Correct 24 ms 1128 KB Correct
12 Correct 24 ms 1100 KB Correct
13 Correct 24 ms 1192 KB Correct

Subtask #3-1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3-2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #4-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #4-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #5-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #5-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #6-1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #6-2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #7-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #7-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Not correct
2 Halted 0 ms 0 KB -