oj.uz

Submission #1022064

# Submission time Handle Problem Language Result Execution time Memory
1022064 2024-07-13T09:32:22 Z ZanP Mechanical Doll (IOI18_doll) C++17
85.5534 / 100
 67 ms 19040 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) {
    int n = A.size();
    vector<vector<int>> repetitions;
    repetitions.resize(M+1);
    vector<int> c(M+1,0);
    for (int i = 0; i < n - 1; i++) {
        repetitions[A[i]].push_back(A[i + 1]);
    }
    repetitions[A[n - 1]].push_back(0);

    for (int i = 1; i <= M; i++)
    {
        int m = repetitions[i].size(), mxtwo = 1;
        while (mxtwo < m) { mxtwo *= 2; }
        if (m == 0) { continue; }
        if (m == 1) {
            c[i] = repetitions[i][0];
        }
        else {
            c[i] = -(int)xyswitches.size() - 1;
            make_switches(repetitions[i].size(), mxtwo - m, xyswitches.size() + 1);
            for (int j = 0; j < repetitions[i].size(); j++) {
                connect(repetitions[i][j], c[i]);
            }
        }
    }

    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; }
                else 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++) {
        if (c[i] < 0) {
            int cid = -(c[i]) - 1;
            if (!xyswitches[cid].active) { c[i] = xyswitches[cid].x; }
            else {
                int cdif = sum - sums[cid];
                c[i] = -(cid - cdif) - 1;
            }
        }
    }

    int s = xyswitches.size();
    vector<int> x, y;
    x.reserve(s);
    y.reserve(s);
    c[0] = A[0];
    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);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:85:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for (int j = 0; j < repetitions[i].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 18 ms 6744 KB Output is correct
3 Correct 14 ms 5724 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 20 ms 8540 KB Output is correct
7 Correct 0 ms 344 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 18 ms 6744 KB Output is correct
3 Correct 14 ms 5724 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 20 ms 8540 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 29 ms 9464 KB Output is correct
9 Correct 34 ms 10268 KB Output is correct
10 Correct 51 ms 14288 KB Output is correct
11 Correct 1 ms 348 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 18 ms 6744 KB Output is correct
3 Correct 14 ms 5724 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 20 ms 8540 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 29 ms 9464 KB Output is correct
9 Correct 34 ms 10268 KB Output is correct
10 Correct 51 ms 14288 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 54 ms 16872 KB Output is correct
15 Correct 30 ms 8768 KB Output is correct
16 Correct 50 ms 13204 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 53 ms 15128 KB Output is correct
21 Correct 1 ms 344 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 436 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 344 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 30 ms 5356 KB Output is correct
3 Correct 33 ms 6992 KB Output is correct
4 Correct 48 ms 8500 KB Output is correct

Subtask #6
41.5533523496 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 30 ms 5356 KB Output is correct
3 Correct 33 ms 6992 KB Output is correct
4 Correct 48 ms 8500 KB Output is correct
5 Partially correct 60 ms 19040 KB Output is partially correct
6 Partially correct 67 ms 18848 KB Output is partially correct
7 Partially correct 59 ms 18972 KB Output is partially correct
8 Partially correct 53 ms 17824 KB Output is partially correct
9 Correct 51 ms 7680 KB Output is correct
10 Correct 62 ms 14704 KB Output is correct
11 Partially correct 46 ms 15544 KB Output is partially correct
12 Partially correct 30 ms 10432 KB Output is partially correct
13 Partially correct 37 ms 12388 KB Output is partially correct
14 Partially correct 50 ms 12288 KB Output is partially correct
15 Partially correct 41 ms 12628 KB Output is partially correct
16 Partially correct 1 ms 604 KB Output is partially correct
17 Partially correct 29 ms 10004 KB Output is partially correct
18 Partially correct 33 ms 9860 KB Output is partially correct
19 Partially correct 29 ms 9924 KB Output is partially correct
20 Partially correct 47 ms 15284 KB Output is partially correct
21 Partially correct 46 ms 14940 KB Output is partially correct
22 Partially correct 60 ms 14900 KB Output is partially correct