oj.uz

Submission #1022089

# Submission time Handle Problem Language Result Execution time Memory
1022089 2024-07-13T09:57:25 Z ZanP Mechanical Doll (IOI18_doll) C++14
100 / 100
 86 ms 15372 KB 
#include "doll.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
void answer(vector<int> C, vector<int> X, vector<int> Y);
struct xyswitch {
    int x, y;
    int par = 0;
    bool gox = true;
    bool active = true;
    xyswitch() {}
    xyswitch(int x, int y) { this->x = x; this->y = y; }
};

vector<xyswitch> xyswitches;

void make_switches(int m, int filler, int base_switch) {
    int f1 = min(filler, (m + filler) / 2), f2 = filler - f1;
    int s1 = ((m + filler) / 2) - f1, s2 = ((m + filler) / 2) - f2;

    xyswitches.push_back(xyswitch());
    int sn = xyswitches.size() - 1;
    if (s1 == 0) { xyswitches[sn].x = -base_switch; }
    else if (s1 == 1 && f1 == 0) {
        xyswitches[sn].x = 0;
    }
    else {
        xyswitches[sn].x = -((int)xyswitches.size() + 1);
        make_switches(s1, f1, base_switch);
        xyswitches[-(xyswitches[sn].x) - 1].par = -(sn + 1);
    }

    if (s2 == 1 && f2 == 0) {
        xyswitches[sn].y = 0;
    }
    else {
        xyswitches[sn].y = -((int)xyswitches.size() + 1);
        make_switches(s2, f2, base_switch);
        xyswitches[-(xyswitches[sn].y) - 1].par = -(sn + 1);
    }
}

void connect(int val, int swid)
{
    xyswitch & sw = xyswitches[-(swid)-1];
    if (sw.gox)
    {
        sw.gox = !sw.gox;
        if (sw.x == 0) { sw.x = val; }
        else { connect(val, sw.x); }
    }
    else
    {
        sw.gox = !sw.gox;
        if (sw.y == 0) { sw.y = val; }
        else { connect(val, sw.y); }
    }
}


void create_circuit(int M, std::vector<int> A) {
    A.push_back(0);
    int n = A.size();
    vector<int> c(M+1,0);

    int m = n, mxtwo = 1;
    while (mxtwo < m) { mxtwo *= 2; }
    make_switches(n, mxtwo - n, xyswitches.size() + 1);
    for (int j = 0; j < n; j++) {
        connect(A[j], -1);
    }

    vector<int> sums(xyswitches.size()); int sum = 0;
    for (int i = xyswitches.size() - 1; i >= 0; i--) {
        xyswitch & sw = xyswitches[i];
        if (sw.x == sw.y) {
            sw.active = false;
            sum++;
            if (sw.par != 0) {
                xyswitch& swpar = xyswitches[-(sw.par) - 1];
                if (swpar.x == -(i + 1)) { swpar.x = sw.x; }
                if (swpar.y == -(i + 1)) { swpar.y = sw.y; }
            }
        }
        sums[i] = sum;
    }

    for (int i = xyswitches.size() - 1; i >= 0; i--) {
        xyswitch& sw = xyswitches[i];
        if (sw.x < 0) {
            int xid = -(sw.x) - 1;
            int xdif = sum - sums[xid];
            sw.x = -(xid - xdif) - 1;
        }
        if (sw.y < 0) {
            int yid = -(sw.y) - 1;
            int ydif = sum - sums[yid];
            sw.y = -(yid - ydif) - 1;
        }

    }

    for (int i = 0; i < M+1; i++) {
        c[i] = -1;
    }

    int s = xyswitches.size();
    vector<int> x, y;
    x.reserve(s);
    y.reserve(s);
    for (int i = 0; i < s; i++) {
        if (!xyswitches[i].active)continue;
        x.push_back(xyswitches[i].x);
        y.push_back(xyswitches[i].y);
    }
    answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 28 ms 5700 KB Output is correct
3 Correct 33 ms 5572 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 37 ms 8352 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 28 ms 5700 KB Output is correct
3 Correct 33 ms 5572 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 37 ms 8352 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 50 ms 10172 KB Output is correct
9 Correct 51 ms 10688 KB Output is correct
10 Correct 86 ms 15372 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 28 ms 5700 KB Output is correct
3 Correct 33 ms 5572 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 37 ms 8352 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 50 ms 10172 KB Output is correct
9 Correct 51 ms 10688 KB Output is correct
10 Correct 86 ms 15372 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 73 ms 14792 KB Output is correct
15 Correct 51 ms 9668 KB Output is correct
16 Correct 73 ms 14456 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 76 ms 15104 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 36 ms 6520 KB Output is correct
3 Correct 33 ms 6616 KB Output is correct
4 Correct 49 ms 8516 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 36 ms 6520 KB Output is correct
3 Correct 33 ms 6616 KB Output is correct
4 Correct 49 ms 8516 KB Output is correct
5 Correct 73 ms 14344 KB Output is correct
6 Correct 74 ms 14120 KB Output is correct
7 Correct 77 ms 14132 KB Output is correct
8 Correct 71 ms 13864 KB Output is correct
9 Correct 44 ms 7360 KB Output is correct
10 Correct 75 ms 12836 KB Output is correct
11 Correct 80 ms 13352 KB Output is correct
12 Correct 46 ms 8896 KB Output is correct
13 Correct 48 ms 9156 KB Output is correct
14 Correct 48 ms 9408 KB Output is correct
15 Correct 48 ms 9412 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 45 ms 8944 KB Output is correct
18 Correct 46 ms 8880 KB Output is correct
19 Correct 61 ms 8804 KB Output is correct
20 Correct 73 ms 13612 KB Output is correct
21 Correct 77 ms 13720 KB Output is correct
22 Correct 71 ms 13356 KB Output is correct