oj.uz

Submission #1014328

# Submission time Handle Problem Language Result Execution time Memory
1014328 2024-07-04T16:42:28 Z c2zi6 Mechanical Doll (IOI18_doll) C++14
100 / 100
 126 ms 24488 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "doll.h"

namespace TEST4 {
    typedef VI::iterator VIT;
    void solve(int M, VI A) { int N = A.size();
        VI C, X, Y;
        X.reserve(2*A.size());
        Y.reserve(2*A.size());
        C = VI(M+1);
        replr(u, 0, M) C[u] = -1;
        auto trans = [&](int x) {
            return -(x+1);
        };
        auto flip = [&](int x, int s) {
            rep(i, s/2) {
                int ch = bool(x&(1<<i))^bool(x&(1<<(s-1-i)));
                x ^= (ch<<i);
                x ^= (ch<<(s-1-i));
            }
            return x;
        };
        auto index = [&](VIT it) {
            if (X.begin() <= it && it < X.end()) {
                return it-X.begin();
            }
            return it-Y.begin();
        };
        int sz = 0;
        while ((1<<sz) < N+1) sz++;
        sz--;
        int l = (1<<sz)-1;
        int r = l+(1<<sz)-1;
        rep(i, r+1) {
            X.pb(-1), Y.pb(-1);
        }
        replr(i, 0, l-1) {
            X[i] = trans(2*i+1);
            Y[i] = trans(2*i+2);
        }
        vector<pair<int, VIT>> order;
        int hmin = N+1;
        reprl(i, r, l) {
            order.pb({flip(2*(i-l)+1, sz+1), Y.begin() + i});
            if (!--hmin) break;
            order.pb({flip(2*(i-l),   sz+1), X.begin() + i});
            if (!--hmin) break;
        }
        sort(all(order));
        A.pb(0);
        VI ka(r+1);
        ka[0] = true;
        rep(u, A.size()) {
            *(order[u].ss) = A[u];
            int v = index(order[u].ss);
            while (v != 0) {
                ka[v] = true;
                v = (v-1)/2;
            }
        }
        map<int, int> compress;
        int c = -1;
        VI xtmp, ytmp;
        rep(u, r+1) if (ka[u]) {
            xtmp.pb(X[u]), ytmp.pb(Y[u]);
            compress[trans(u)] = c--;
        }
        X = xtmp;
        Y = ytmp;
        rep(u, X.size()) {
            if (X[u] < 0) {
                if (compress.count(X[u])) {
                    X[u] = compress[X[u]];
                } else {
                    X[u] = -1;
                }
            }
            if (Y[u] < 0) {
                if (compress.count(Y[u])) {
                    Y[u] = compress[Y[u]];
                } else {
                    Y[u] = -1;
                }
            }
        }
        answer(C, X, Y);
    }
};

void create_circuit(int M, VI A) {
    TEST4::solve(M, A);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 39 ms 9628 KB Output is correct
3 Correct 36 ms 9412 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 59 ms 12860 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 39 ms 9628 KB Output is correct
3 Correct 36 ms 9412 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 59 ms 12860 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 83 ms 18616 KB Output is correct
9 Correct 77 ms 19392 KB Output is correct
10 Correct 115 ms 24488 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 39 ms 9628 KB Output is correct
3 Correct 36 ms 9412 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 59 ms 12860 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 83 ms 18616 KB Output is correct
9 Correct 77 ms 19392 KB Output is correct
10 Correct 115 ms 24488 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 119 ms 23720 KB Output is correct
15 Correct 76 ms 18832 KB Output is correct
16 Correct 118 ms 23460 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 117 ms 24036 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 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 1 ms 344 KB Output is correct
2 Correct 87 ms 17696 KB Output is correct
3 Correct 70 ms 17660 KB Output is correct
4 Correct 112 ms 23464 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 87 ms 17696 KB Output is correct
3 Correct 70 ms 17660 KB Output is correct
4 Correct 112 ms 23464 KB Output is correct
5 Correct 119 ms 23468 KB Output is correct
6 Correct 120 ms 23216 KB Output is correct
7 Correct 116 ms 23260 KB Output is correct
8 Correct 118 ms 23836 KB Output is correct
9 Correct 77 ms 17492 KB Output is correct
10 Correct 114 ms 22992 KB Output is correct
11 Correct 112 ms 23796 KB Output is correct
12 Correct 79 ms 18752 KB Output is correct
13 Correct 71 ms 17096 KB Output is correct
14 Correct 81 ms 18360 KB Output is correct
15 Correct 73 ms 17368 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 69 ms 14816 KB Output is correct
18 Correct 71 ms 17332 KB Output is correct
19 Correct 74 ms 17848 KB Output is correct
20 Correct 113 ms 23192 KB Output is correct
21 Correct 126 ms 23468 KB Output is correct
22 Correct 116 ms 22952 KB Output is correct