Submission #1014122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014122		c2zi6	Mechanical Doll (IOI18_doll)	C++14	46 / 100	81 ms	18768 KiB

doll

#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;*/
        while (X.size() < 2*N) {
            X.pb(0), Y.pb(0);
        }
        answer(C, X, Y);
    }
};

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

Compilation message (stderr)

doll.cpp: In function 'void TEST6::solve(int, VI)':
doll.cpp:138:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  138 |         while (X.size() < 2*N) {
      |                ~~~~~~~~~^~~~~
doll.cpp:94:14: warning: variable 'print' set but not used [-Wunused-but-set-variable]
   94 |         auto print = [&](VIT it) {
      |              ^~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 18 / 18
• Subtask 6: 28 / 56