oj.uz

Submission #139420

# Submission time Handle Problem Language Result Execution time Memory
139420 2019-07-31T16:24:10 Z qrno Mechanical Doll (IOI18_doll) C++14
9 / 100
 92 ms 11748 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3404 KB wrong serial number
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3404 KB wrong serial number
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3404 KB wrong serial number
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3404 KB wrong serial number
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 3404 KB Output is partially correct
2 Correct 47 ms 7640 KB Output is correct
3 Partially correct 80 ms 11556 KB Output is partially correct
4 Partially correct 91 ms 11392 KB Output is partially correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 3404 KB Output is partially correct
2 Correct 47 ms 7640 KB Output is correct
3 Partially correct 80 ms 11556 KB Output is partially correct
4 Partially correct 91 ms 11392 KB Output is partially correct
5 Incorrect 92 ms 11748 KB wrong serial number
6 Halted 0 ms 0 KB -