Submission #139425

#	Time	Username	Problem	Language	Result	Execution time	Memory
139425		qrno	Mechanical Doll (IOI18_doll)	C++14	0 / 100	3 ms	2656 KiB

doll

#include "doll.h"

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100100;
const int NONE = 123456;

vector<int> X, Y;

vector<int> neigh[MAXN];

int sCount = -1;
int createSwitch(int x, int y) {

    X.push_back(x);
    Y.push_back(y);

    return sCount--;
}

int createTree(vector<int> &neigh) {
    int ROOT = sCount-14;
    int last = neigh[neigh.size()-1];

    int ns = (int)neigh.size();

    neigh[ns-1] = ROOT;
    for (int i = 0; i < 16-ns; i++)
        neigh.push_back(ROOT);
    neigh[15] = last;

    int a1 = createSwitch(neigh[0], neigh[8]);
    int a2 = createSwitch(neigh[4], neigh[12]);
    int a3 = createSwitch(neigh[2], neigh[10]);
    int a4 = createSwitch(neigh[6], neigh[14]);
    int a5 = createSwitch(neigh[1], neigh[9]);
    int a6 = createSwitch(neigh[5], neigh[13]);
    int a7 = createSwitch(neigh[3], neigh[11]);
    int a8 = createSwitch(neigh[7], neigh[15]);

    int b1 = createSwitch(a1, a2);
    int b2 = createSwitch(a3, a4);
    int b3 = createSwitch(a5, a6);
    int b4 = createSwitch(a7, a8);

    int c1 = createSwitch(b1, b2);
    int c2 = createSwitch(b3, b4);

    int x = createSwitch(c1, c2);

    return x;
}

void printAns(vector<int> C, vector<int> X, vector<int> Y) {
    cout << "C: ";
    for (int x : C)
        cout << x << " ";
    cout << endl;

    cout << "(X, Y): ";
    for (int i = 0; i < (int)X.size(); i++) {
        cout << "((" << -(i+1) << "))=";
        cout << "(" << X[i] << ", "
            << Y[i] << ")   ";
        if (!((i+1)%5)) cout << endl;
    }
    cout << endl;
}


void create_circuit(int M, vector<int> A) {
    vector<int> C(M+1, NONE);

    A.push_back(0);
    for (int i = 0; i < (int)A.size()-1; i++) {
        neigh[A[i]].push_back(A[i+1]);
    }

    for (int i = 1; i <= M; i++)
        if (!neigh[i].size())
            neigh[i].push_back(0);


    C[0] = A[0];
    for (int i = 1; i <= M; i++) {
        C[i] = createTree(neigh[i]);
    }

    for (int i = 1; i <= M; i++) {
        if (C[i] == NONE)
            C[i] = 0;
    }

    answer(C, X, Y);
}

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