oj.uz

Submission #782000

# Submission time Handle Problem Language Result Execution time Memory
782000 2023-07-13T14:39:50 Z faruk Mechanical Doll (IOI18_doll) C++17
37 / 100
 95 ms 14656 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

void set_idxs(int offset, int curr, int idx, int depth, int &max_node, vector<int> &targets, vector<int> &xs, vector<int> &ys) {
    if (curr >= max_node) {
        int par = (curr - 1) / 2; 
        if (curr % 2)
            xs[par] = targets[idx];
        else
            ys[par] = targets[idx];
        return;
    }
    xs[curr] = -((curr + 1) * 2 - 1) - offset;
    ys[curr] = -((curr + 1) * 2) - offset;
    set_idxs(offset, (curr + 1) * 2 - 1, idx, depth + 1, max_node, targets, xs, ys);
    set_idxs(offset, (curr + 1) * 2, idx + (1 << depth), depth + 1, max_node, targets, xs, ys);
}

pair<vector<int>, vector<int> > getxy(int node, vector<int> targets, int offset) {
    // determine size of last_row
    int siz = 1, needed_nodes = 1;
    while (siz * 2 < targets.size())
        siz *= 2, needed_nodes += siz;
    
    while (targets.size() < 2*siz) {
        targets.push_back(-node);
        swap(targets[targets.size() - 1], targets[targets.size() - 2]);
    }

    vector<int> xs(needed_nodes);
    vector<int> ys(needed_nodes);
    set_idxs(offset, 0, 0, 0, needed_nodes, targets, xs, ys);
    return make_pair(xs, ys);
}

void create_circuit(int M, std::vector<int> A) {
    int N = A.size();
    std::vector<int> C(M + 1);
    std::vector<int> X(M), Y(M);
    C[0] = A[0];
    for (int i = 1; i <= M; ++i)
        C[i] = -i;
    for (int i = 0; i < M; i++)
        X[i] = -(i + 1);

    vector<vector<int> > targets(M + 1);
    for (int i = 0; i < A.size(); i++) {
        int next = i == A.size() - 1 ? 0 : A[i + 1];
        targets[A[i]].push_back(next);
    }

    for (int i = 1; i <= M; i++) {
        if (targets[i].empty())
            continue;
        Y[i - 1] = -(X.size() + 1);
        auto xandy = getxy(i, targets[i], X.size() + 1);
        for (int j = 0; j < xandy.first.size(); j++)
            X.push_back(xandy.first[j]), Y.push_back(xandy.second[j]);
    }

    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > getxy(int, std::vector<int>, int)':
doll.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     while (siz * 2 < targets.size())
      |            ~~~~~~~~^~~~~~~~~~~~~~~~
doll.cpp:27:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     while (targets.size() < 2*siz) {
      |            ~~~~~~~~~~~~~~~^~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < A.size(); i++) {
      |                     ~~^~~~~~~~~~
doll.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         int next = i == A.size() - 1 ? 0 : A[i + 1];
      |                    ~~^~~~~~~~~~~~~~~
doll.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int j = 0; j < xandy.first.size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~
doll.cpp:39:9: warning: unused variable 'N' [-Wunused-variable]
   39 |     int N = A.size();
      |         ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000018 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Correct 29 ms 6356 KB Output is correct
3 Partially correct 50 ms 10808 KB Output is partially correct
4 Partially correct 57 ms 11528 KB Output is partially correct

Subtask #6
28.0000000056 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Correct 29 ms 6356 KB Output is correct
3 Partially correct 50 ms 10808 KB Output is partially correct
4 Partially correct 57 ms 11528 KB Output is partially correct
5 Partially correct 86 ms 14504 KB Output is partially correct
6 Partially correct 88 ms 14436 KB Output is partially correct
7 Partially correct 83 ms 14500 KB Output is partially correct
8 Partially correct 85 ms 14656 KB Output is partially correct
9 Partially correct 50 ms 8992 KB Output is partially correct
10 Partially correct 80 ms 14040 KB Output is partially correct
11 Partially correct 95 ms 14564 KB Output is partially correct
12 Partially correct 51 ms 9780 KB Output is partially correct
13 Partially correct 54 ms 9748 KB Output is partially correct
14 Partially correct 56 ms 9500 KB Output is partially correct
15 Partially correct 68 ms 9760 KB Output is partially correct
16 Partially correct 2 ms 552 KB Output is partially correct
17 Partially correct 44 ms 8104 KB Output is partially correct
18 Partially correct 41 ms 8068 KB Output is partially correct
19 Partially correct 43 ms 8492 KB Output is partially correct
20 Partially correct 59 ms 11224 KB Output is partially correct
21 Partially correct 68 ms 13116 KB Output is partially correct
22 Partially correct 55 ms 10628 KB Output is partially correct