oj.uz

Submission #1078357

# Submission time Handle Problem Language Result Execution time Memory
1078357 2024-08-27T15:48:42 Z belgianbot Mechanical Doll (IOI18_doll) C++17
46 / 100
 83 ms 13096 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first 
#define se second

using namespace std;

vector<vector<int>> adj;
vector<int> C, X, Y;

int cnt = -1;

void divide(vector<int> *a, int prev) {
    if (a->size() == 2) {
        X.pb((*a)[0]);
        Y.pb((*a)[1]);
        return;
    }

    vector<int> b, c;
    for (int i = 0; i < a->size(); i++) {
        if (i & 1) c.pb( (*a)[i]);
        else b.pb((*a)[i]);
    }
    if (b.size() > c.size()) {
        c.pb(b.back());
        b.back() = prev;
    }
    X.pb(cnt); cnt--; Y.pb(0); int n = Y.size();
    divide(&b, cnt + 1);
    Y[n - 1] = cnt; cnt--;
    divide(&c, cnt + 1);
}
void build(int x) {
    int n = adj[x].size();
    if (!n) adj[x].pb(x);
    if (n == 1) C[x] = adj[x][0];
    else if (n) {
        C[x] = cnt; cnt--;
        divide(&adj[x], cnt + 1);
    }

} 
void create_circuit(int M, vector<int> A) {
    if (M == 1) {
            int N = A.size();
    A.push_back(0);
    vector<int> C(M + 1, INT_MAX), X, Y;
    C[0] = A[0];
 
    int time = N - 1;
    vector<pair<int,int>> fact = {{1, 1}};
    int cnt = -1;
    while (time) {
        int next = 0;
        for (auto x : fact) {
            if (time % x.first == 0) {
                time -= x.first;
                next = x.first;
                X.push_back(x.second);
                if (cnt != -1) Y.push_back(cnt);
                else C[1] = cnt;
                cnt--;
                break;
            }
        }
        for (auto &x : fact) x.first += next;
        fact.push_back({next, cnt + 1});
    }
    if (cnt != -1) Y.push_back(0);
    else C[1] = 0;
    answer(C, X, Y);
    return;
    }
    int N = A.size();
    A.push_back(0);
    C.resize(M + 1, -1);

    /*adj.resize(M + 1);
    adj[0].pb(A[0]); C[0] = A[0];
    for (int i = 1; i <= N; i++) adj[A[i-1]].pb(A[i]);*/

    cnt--;
    divide(&A, -1);
    //for (int i = 1; i <= M; i++) build(i);

    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void divide(std::vector<int>*, int)':
doll.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < a->size(); i++) {
      |                     ~~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:76:9: warning: unused variable 'N' [-Wunused-variable]
   76 |     int N = A.size();
      |         ^

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 10 ms 2864 KB Output is correct
3 Correct 10 ms 2904 KB Output is correct
4 Correct 14 ms 4180 KB Output is correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 10 ms 2864 KB Output is correct
3 Correct 10 ms 2904 KB Output is correct
4 Correct 14 ms 4180 KB Output is correct
5 Partially correct 66 ms 13092 KB Output is partially correct
6 Partially correct 67 ms 13096 KB Output is partially correct
7 Partially correct 61 ms 13036 KB Output is partially correct
8 Partially correct 64 ms 12872 KB Output is partially correct
9 Partially correct 58 ms 11668 KB Output is partially correct
10 Partially correct 61 ms 12880 KB Output is partially correct
11 Partially correct 60 ms 12512 KB Output is partially correct
12 Partially correct 59 ms 11840 KB Output is partially correct
13 Partially correct 72 ms 12212 KB Output is partially correct
14 Partially correct 59 ms 12100 KB Output is partially correct
15 Partially correct 83 ms 12216 KB Output is partially correct
16 Partially correct 2 ms 604 KB Output is partially correct
17 Correct 34 ms 6896 KB Output is correct
18 Partially correct 58 ms 11932 KB Output is partially correct
19 Partially correct 55 ms 11840 KB Output is partially correct
20 Partially correct 63 ms 12812 KB Output is partially correct
21 Partially correct 62 ms 12584 KB Output is partially correct
22 Partially correct 65 ms 12588 KB Output is partially correct