oj.uz

Submission #995432

# Submission time Handle Problem Language Result Execution time Memory
995432 2024-06-09T05:10:23 Z shiomusubi496 Mechanical Doll (IOI18_doll) C++17
15 / 100
 88 ms 16244 KB 
#include "doll.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)

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; }

void create_circuit(int M, std::vector<int> A) {
    int N = A.size();
    vector<vector<int>> B(M + 1);
    rep (i, N) B[A[i]].push_back(i);
    vector<int> C(M + 1);
    C[0] = A[0];
    int cur = 1;
    int lst = -1;
    vector<pair<int, int>> memo;
    rep2 (i, 1, M + 1) {
        if (B[i].empty()) {
            C[i] = 0;
            continue;
        }
        if (B[i].size() == 1) {
            if (B[i][0] < N - 1) C[i] = A[B[i][0] + 1];
            else lst = i;
            continue;
        }
        int lev = 0;
        while ((1 << lev) < B[i].size()) ++lev;
        if ((1 << lev) != B[i].size()) {
            memo.emplace_back(i, -1);
        }
        int r = 1;
        auto dfs = [&](auto&& dfs, int v, vector<int> p, int lev, bool f) -> void {
            if (lev == 0) {
                if (p.empty()) {
                    if (f) memo.back().second = v;
                    else C[v] = r;
                }
                else {
                    assert(p.size() == 1);
                    if (p[0] < N - 1) C[v] = A[p[0] + 1];
                    else lst = v;
                }
                return;
            }
            vector<int> p0, p1;
            rep (i, p.size()) {
                if (i % 2 == 0) p0.push_back(p[i]);
                else p1.push_back(p[i]);
            }
            int t = cur++;
            if (r == 1) r = -t;
            C.push_back(0); C.push_back(0);
            C[v] = -t;
            int tmp = C.size();
            dfs(dfs, tmp - 2, p0, lev - 1, false);
            dfs(dfs, tmp - 1, p1, lev - 1, f);
        };
        dfs(dfs, i, B[i], lev, true);
        if ((1 << lev) != B[i].size()) memo.back().first = r;
    }
    {
        if (memo.empty()) C[lst] = 0;
        else {
            C[lst] = memo[0].first;
            rep (i, memo.size() - 1) {
                C[memo[0].second] = memo[i + 1].first;
            }
            C[memo.back().second] = 0;
        }
    }
    vector<int> X(cur - 1), Y(cur - 1);
    rep (i, cur - 1) {
        X[i] = C[M + 1 + i * 2];
        Y[i] = C[M + 1 + i * 2 + 1];
    }
    C.resize(M + 1);
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:37:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while ((1 << lev) < B[i].size()) ++lev;
      |                ~~~~~~~~~~~^~~~~~~~~~~~~
doll.cpp:38:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if ((1 << lev) != B[i].size()) {
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~
doll.cpp:69:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         if ((1 << lev) != B[i].size()) memo.back().first = r;
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 22 ms 6748 KB Output is correct
3 Correct 16 ms 5724 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 3932 KB Output is correct
6 Correct 23 ms 8476 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 22 ms 6748 KB Output is correct
3 Correct 16 ms 5724 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 3932 KB Output is correct
6 Correct 23 ms 8476 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 38 ms 8784 KB Output is correct
9 Correct 45 ms 10008 KB Output is correct
10 Correct 56 ms 13240 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 22 ms 6748 KB Output is correct
3 Correct 16 ms 5724 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 3932 KB Output is correct
6 Correct 23 ms 8476 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 38 ms 8784 KB Output is correct
9 Correct 45 ms 10008 KB Output is correct
10 Correct 56 ms 13240 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Incorrect 75 ms 14892 KB state 'Y'
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Output is partially correct
2 Correct 47 ms 7448 KB Output is correct
3 Partially correct 68 ms 12608 KB Output is partially correct
4 Partially correct 88 ms 14132 KB Output is partially correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Output is partially correct
2 Correct 47 ms 7448 KB Output is correct
3 Partially correct 68 ms 12608 KB Output is partially correct
4 Partially correct 88 ms 14132 KB Output is partially correct
5 Incorrect 87 ms 16244 KB state 'Y'
6 Halted 0 ms 0 KB -