oj.uz

Submission #1014327

# Submission time Handle Problem Language Result Execution time Memory
1014327 2024-07-04T16:41:22 Z c2zi6 Mechanical Doll (IOI18_doll) C++14
100 / 100
 124 ms 25904 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 TEST5 {
    void solve(int M, VI A) {
        int N = A.size();
        VI C;
        VI X;
        VI Y;
        if (A.size() == 1) {
            C.pb(1);
            C.pb(0);
            answer(C, X, Y);
            return;
        }
        C.pb(1);
        C.pb(-1);
        int s = 0;
        while ((1<<s) < N) s++;
        replr(i, 2, s+1) {
            X.pb(-1);
            Y.pb(-i);
        }
        Y.back() = 0;
        int n = N-1;
        rep(i, s) {
            if (n & (1<<i)) {
                X[s-1-i] = 1;
            }
        }
        answer(C, X, Y);
    }
};
namespace TEST6 {
    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);
        
        VI cnt(M+1);
        for (int x : A) cnt[x]++;
        VI lwb(N+1);
        replr(i, 0, N) {
            int x = 0;
            while ((1<<x) < i) x++;
            lwb[i] = x;
        }

        VI sw(M+1, -1);
        vector<vector<VIT>> order(M+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 print = [&](VIT it) {
            if (X.begin() <= it && it < X.end()) {
                cout << "X[" << it-X.begin() << "]";
            } else {
                cout << "Y[" << it-Y.begin() << "]";
            }
        };
        VI turn(M+1);
        int u = 0;
        for (int v : A) {
            if (cnt[u] > 1) {
                int sz = lwb[cnt[u]];
                if (sw[u] == -1) {
                    sw[u] = X.size();
                    C[u] = trans(sw[u]);
                    int l = (1<<(sz-1))-1;
                    int r = (1<<sz)-2;
                    replr(i, 0, r) {
                        X.pb(0), Y.pb(0);
                    }
                    replr(i, 0, l-1) {
                        /*cout << trans(sw[u]+2*i+1) << endl;*/
                        /*cout << trans(sw[u]+2*i+2) << endl;*/
                        X[sw[u]+i] = trans(sw[u] + 2*i+1);
                        Y[sw[u]+i] = trans(sw[u] + 2*i+2);
                    }
                    order[u] = vector<VIT>(1<<sz);
                    replr(i, l, r) {
                        order[u][flip(i*2+1-(r+1), sz)] = X.begin() + sw[u]+i;
                        order[u][flip(i*2+2-(r+1), sz)] = Y.begin() + sw[u]+i;
                    }
                    rep(i, (1<<sz)-cnt[u]) {
                        *(order[u][i]) = trans(sw[u]);
                    }
                    turn[u] = (1<<sz)-cnt[u];
                }
                *(order[u][turn[u]++]) = v;
            } else {
                C[u] = v;
            }
            u = v;
        }
        /*rep(u, C.size()) cout << u << ": " << C[u] << endl;*/
        /*rep(u, X.size()) cout << trans(u) << ": " << X[u] << ", " << Y[u] << endl;*/
        answer(C, X, Y);
    }
};
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 print = [&](VIT it) {
            if (X.begin() <= it && it < X.end()) {
                cout << "X[" << it-X.begin() << "]";
            } else {
                cout << "Y[" << it-Y.begin() << "]";
            }
        };
        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--;

        /*cout << "TREE HAS " << (1<<sz) << " LEAVES" << endl;*/
        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;
            }
        }

        /*rep(u, C.size()) cout << u << ": " << C[u] << endl;*/
        /*rep(u, X.size()) cout << trans(u) << ": " << X[u] << ", " << Y[u] << endl;*/

        map<int, int> compress;
        /*cout << "dont neet to delete: ";*/
        int c = -1;
        VI xtmp, ytmp;
        rep(u, r+1) if (ka[u]) {
            /*cout << trans(u) << " ";*/
            xtmp.pb(X[u]), ytmp.pb(Y[u]);
            compress[trans(u)] = c--;
        }
        /*cout << endl;*/
        /*for (auto p : compress) cout << p.ff << " becomes " << p.ss << endl;*/
        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;
                }
            }
        }
        /*rep(u, C.size()) cout << u << ": " << C[u] << endl;*/
        /*rep(u, X.size()) cout << trans(u) << ": " << X[u] << ", " << Y[u] << endl;*/
        /*rep(u, X.size()) cout << trans(u) << " " << X[u] << endl;*/
        /*rep(u, X.size()) cout << trans(u) << " " << Y[u] << endl;*/
        answer(C, X, Y);
    }
};

void create_circuit(int M, VI A) {
    TEST4::solve(M, A);
    return;
    if (M == 1) TEST5::solve(M, A);
    else TEST4::solve(M, A);
}

Compilation message

doll.cpp: In function 'void TEST6::solve(int, VI)':
doll.cpp:94:14: warning: variable 'print' set but not used [-Wunused-but-set-variable]
   94 |         auto print = [&](VIT it) {
      |              ^~~~~
doll.cpp: In function 'void TEST4::solve(int, VI)':
doll.cpp:160:14: warning: variable 'print' set but not used [-Wunused-but-set-variable]
  160 |         auto print = [&](VIT it) {
      |              ^~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 34 ms 10040 KB Output is correct
3 Correct 33 ms 9672 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 55 ms 13616 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 344 KB Output is correct
2 Correct 34 ms 10040 KB Output is correct
3 Correct 33 ms 9672 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 55 ms 13616 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 71 ms 19896 KB Output is correct
9 Correct 71 ms 19720 KB Output is correct
10 Correct 116 ms 25512 KB Output is correct
11 Correct 1 ms 344 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 344 KB Output is correct
2 Correct 34 ms 10040 KB Output is correct
3 Correct 33 ms 9672 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 55 ms 13616 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 71 ms 19896 KB Output is correct
9 Correct 71 ms 19720 KB Output is correct
10 Correct 116 ms 25512 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 105 ms 25328 KB Output is correct
15 Correct 64 ms 18880 KB Output is correct
16 Correct 107 ms 25008 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 432 KB Output is correct
20 Correct 114 ms 25904 KB Output is correct
21 Correct 0 ms 344 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 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 364 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 66 ms 18856 KB Output is correct
3 Correct 75 ms 19732 KB Output is correct
4 Correct 108 ms 25028 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 66 ms 18856 KB Output is correct
3 Correct 75 ms 19732 KB Output is correct
4 Correct 108 ms 25028 KB Output is correct
5 Correct 110 ms 25020 KB Output is correct
6 Correct 105 ms 24668 KB Output is correct
7 Correct 110 ms 24744 KB Output is correct
8 Correct 108 ms 24488 KB Output is correct
9 Correct 80 ms 18080 KB Output is correct
10 Correct 115 ms 25004 KB Output is correct
11 Correct 124 ms 24488 KB Output is correct
12 Correct 71 ms 18368 KB Output is correct
13 Correct 74 ms 19088 KB Output is correct
14 Correct 82 ms 18360 KB Output is correct
15 Correct 73 ms 18868 KB Output is correct
16 Correct 2 ms 856 KB Output is correct
17 Correct 63 ms 15552 KB Output is correct
18 Correct 83 ms 19732 KB Output is correct
19 Correct 71 ms 18828 KB Output is correct
20 Correct 112 ms 25260 KB Output is correct
21 Correct 107 ms 24408 KB Output is correct
22 Correct 106 ms 24492 KB Output is correct