Submission #288525

#	Time	Username	Problem	Language	Result	Execution time	Memory
288525		andrew	자동 인형 (IOI18_doll)	C++17	37 / 100	535 ms	22212 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"

#define fi first
#define se second
#define p_b push_back
#define m_p make_pair
#define sz(x) (int)x.size()
#define pii pair <int, int>
#define all(x) x.begin(),x.end()

using namespace std;
typedef long long ll;
const ll inf = 1e7;

ll stn = 0, id = -1, uk;

vector <int> x, y, st, l, r, idx, le, ri;

int build(int v, int tl, int tr){
    le[v] = tl;
    ri[v] = tr;
    if(tl == tr)return 0;
    else{
        int tm = (tl + tr) >> 1;
        int t = stn, d = id;
        idx[v] = t;
        stn++;
        id--;
        l[v] = sz(l);

        l.p_b(0);
        r.p_b(0);
        le.p_b(0);
        ri.p_b(0);

        x.p_b(0);
        y.p_b(0);

        idx.p_b(0);

        r[v] = sz(l);

        l.p_b(0);
        r.p_b(0);
        le.p_b(0);
        ri.p_b(0);

        idx.p_b(0);
        int vv = build(l[v], tl, tm);
        x[t] = vv;
        vv = build(r[v], tm + 1, tr);
        y[t] = vv;
        return d;
    }
}

int dfs(int v){
    if(le[v] == ri[v])return st[uk++];
    else{
        int t = idx[v];
        int V = dfs(l[v]);
        if(V != inf){
            x[t] = V;
        }
        swap(l[v], r[v]);
        swap(x[t], y[t]);
        return inf;
    }
}

void create_circuit(int M, vector<int> A) {
    int n = sz(A);
    stn = 0;
    id = -1;
    std::vector<int> C(M + 1);
    vector <vector <int>> v(M + 1);
    if(sz(A) == 1){
        fill(all(C), 0);
        C[0] = A[0];
        C[A[0]] = 0;
        answer(C, x, y);
        return;
    }

    while((sz(A) & (sz(A) + 1)))A.p_b(-1);
    A.p_b(0);

    st = A;
    fill(all(C), -1);
    l.clear();
    le.clear();
    r.clear();
    ri.clear();
    uk = 0;
    l.p_b(0);
    le.p_b(0);
    r.p_b(0);
    ri.p_b(0);
    idx.p_b(0);
    C[0] = build(0, 0, sz(st) - 1);
    uk = 0;
    for(int i = 0; i < sz(st); i++){
        dfs(0);
    }

    answer(C, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:73:9: warning: unused variable 'n' [-Wunused-variable]
   73 |     int n = sz(A);
      |         ^

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