Submission #601496

#	Time	Username	Problem	Language	Result	Execution time	Memory
601496		Mazaalai	Mechanical Doll (IOI18_doll)	C++17	6 / 100	90 ms	11128 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define pb push_back
#define ff first
#define ss second
using namespace std;
using VI = vector <int>;
using PII = pair <int, int>;
int n, m;
void create_circuit(int M, vector<int> nums) {
    m = M;
    n = sz(nums);
    int switchNo = 1; //-1 to -S
    VI C(m+1, 0), X, Y;

    // C -> output of i
    C[0] = nums[0];
    vector <int> child[m+1];
    for (int i = 0; i < n-1; i++) 
        child[nums[i]].pb(nums[i+1]);

    child[nums[n-1]].pb(0);

    for (int i = 1; i <= m; i++) {
        VI& cur = child[i];
        if (cur.empty()) continue;
        int x = sz(cur);
        if (x == 1) {
            C[i] = cur[0];
            continue;
        }
        queue <PII> nx;
        X.pb(cur[0]); 
        Y.pb(cur[1]);
        nx.push({switchNo-1, 0});
        nx.push({switchNo-1, 1});
        C[i] = -(switchNo++);
        for (int j = 2; j < x; j++) {
            PII tmp = nx.front(); nx.pop();
            if (tmp.ss == 0) {
                X.pb(X[tmp.ff]);
                Y.pb(cur[j]);
                nx.push({switchNo-1, 0});
                nx.push({switchNo-1, 1});
                X[tmp.ff] = -(switchNo++);
            } else {
                X.pb(Y[tmp.ff]);
                Y.pb(cur[j]);
                nx.push({switchNo-1, 0});
                nx.push({switchNo-1, 1});
                Y[tmp.ff] = -(switchNo++);
            }
        }
    }
    answer(C, X, Y);
}

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