Submission #139420

#	Time	Username	Problem	Language	Result	Execution time	Memory
139420		qrno	Mechanical Doll (IOI18_doll)	C++14	9 / 100	92 ms	11748 KiB

doll

#include "doll.h"

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

const int NONE = 123456;
const int MAXN = 200200;

vector<int> X, Y;

int sCount = -1;
int createSwitch(int x, int y) {
    X.push_back(x);
    Y.push_back(y);

    return sCount--;
}

pair<int, int> findP2(int repAmount) {
    int p2 = 1;
    int h = 2;

    while (h <= repAmount)
        h *= 2, p2++;

    return make_pair(h, p2);
}

int val[4*MAXN+100];
void makePattern(int csA, int logg) {
    memset(val, -1, sizeof(val));
    csA--;

    val[0] = 0;
    int counter = 0;
    for (int i = 0; i < logg; i++) {
        int diff = (1 << (logg-i-1));
        for (int j = 0; j <= min(csA, 4*MAXN); j += diff) {
            if (val[j] == -1)
                val[j] = val[j-diff]+(1 << i), counter++;
        }
    }

    /*cout << "MADE PATTERN: ";
    for (int i = 0; i < csA+1; i++) {
        cout << val[i] << " ";
    }
    cout << endl << endl;
    */
}

int createTree(int repAmount) {
    pair<int, int> b2 = findP2(repAmount);
    
    int csA = b2.first;
    int logg = b2.second;

    int ROOT = -(csA-1);

    /*
    cout << "CSA " << csA << endl;
    cout << "LOGG " << logg << endl;
    cout << "ROOT " << ROOT << endl;
    */

    makePattern(csA, logg);

    for (int i = 0; i < csA; i++) {
        if (val[i] >= repAmount) {
            val[i] = ROOT;
        } else {
            val[i] = 1;
        }
    }

    val[csA-1] = 0;
/*
    cout << "NEWVALS ";
    for (int i = 0; i < csA; i++) {
        cout << val[i] << " ";
    }
    cout << endl;
   */

    for (int i = 2; i < csA+100; i *= 2) {
        for (int j = 0; j < csA/i; j++) {
            /*
            cout << "VAL[" << j << "] = " << 
                " CREATESWITCH " << val[2*j] << " " << val[2*j+1] << endl;
                */

            val[j] =
                createSwitch(val[2*j], val[2*j+1]);
        }
    }

    return val[0];
}

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);

    int repAmount = A.size();

    C[0] = 1;
    C[1] = createTree(repAmount-1);

    answer(C, X, Y);
}

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