oj.uz

Submission #995505

# Submission time Handle Problem Language Result Execution time Memory
995505 2024-06-09T07:55:20 Z shiomusubi496 Mechanical Doll (IOI18_doll) C++17
100 / 100
 97 ms 8864 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<int> C(M + 1, -1);
    int lev = 0;
    while ((1 << (lev + 1)) <= N) ++lev;
    vector<int> X, Y;
    while (lev >= 0) {
        int n = 1 << lev;
        if (n > N) {
            X.push_back(-1);
            Y.push_back(0);
            --lev;
            if (lev >= 0) Y.back() = -(int)X.size() - 1;
            continue;
        }
        N -= n;
        if (n == 1) {
            X.push_back(1);
            Y.push_back(0);
            --lev;
        }
        else {
            X.push_back(-(int)X.size() - 2);
            Y.push_back(0);
            int idx = Y.size() - 1;
            int tmp = X.size();
            rep2 (i, 1, n / 2) {
                X.push_back(-(tmp + i * 2));
                Y.push_back(-(tmp + i * 2 + 1));
            }
            rep2 (i, n / 2, n) {
                X.push_back(1);
                Y.push_back(1);
            }
            --lev;
            Y[idx] = -(int)X.size() - 1;
        }
    }
    {
        int cur = 0;
        int idx = 0;
        vector<bool> sw(X.size(), true);
        do {
            if (cur >= 0) cur = C[cur];
            else {
                if (sw[-1 - cur]) {
                    sw[-1 - cur] = false;
                    if (X[-1 - cur] > 0) X[-1 - cur] = A[idx++];
                    cur = X[-1 - cur];
                }
                else {
                    sw[-1 - cur] = true;
                    if (Y[-1 - cur] > 0) Y[-1 - cur] = A[idx++];
                    cur = Y[-1 - cur];
                }
            }
        } while (cur != 0);
    }
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 26 ms 4088 KB Output is correct
3 Correct 25 ms 3788 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 39 ms 5320 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 26 ms 4088 KB Output is correct
3 Correct 25 ms 3788 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 39 ms 5320 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 52 ms 6080 KB Output is correct
9 Correct 52 ms 6444 KB Output is correct
10 Correct 79 ms 8864 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 26 ms 4088 KB Output is correct
3 Correct 25 ms 3788 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 39 ms 5320 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 52 ms 6080 KB Output is correct
9 Correct 52 ms 6444 KB Output is correct
10 Correct 79 ms 8864 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 Correct 75 ms 8308 KB Output is correct
15 Correct 58 ms 5672 KB Output is correct
16 Correct 72 ms 8124 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 76 ms 8468 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 45 ms 5312 KB Output is correct
3 Correct 45 ms 5312 KB Output is correct
4 Correct 70 ms 7868 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 45 ms 5312 KB Output is correct
3 Correct 45 ms 5312 KB Output is correct
4 Correct 70 ms 7868 KB Output is correct
5 Correct 97 ms 7948 KB Output is correct
6 Correct 76 ms 7876 KB Output is correct
7 Correct 78 ms 7868 KB Output is correct
8 Correct 70 ms 7872 KB Output is correct
9 Correct 43 ms 5100 KB Output is correct
10 Correct 67 ms 7840 KB Output is correct
11 Correct 68 ms 7800 KB Output is correct
12 Correct 44 ms 5240 KB Output is correct
13 Correct 60 ms 5408 KB Output is correct
14 Correct 47 ms 5692 KB Output is correct
15 Correct 48 ms 5812 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 46 ms 5460 KB Output is correct
18 Correct 43 ms 5312 KB Output is correct
19 Correct 44 ms 5224 KB Output is correct
20 Correct 74 ms 7812 KB Output is correct
21 Correct 74 ms 7868 KB Output is correct
22 Correct 68 ms 7792 KB Output is correct