oj.uz

Submission #1045112

# Submission time Handle Problem Language Result Execution time Memory
1045112 2024-08-05T17:00:10 Z n1k Mechanical Doll (IOI18_doll) C++17
100 / 100
 91 ms 14180 KB 
#include <bits/stdc++.h>
#include "doll.h"
//#include "debug.cpp"

#define debug(...) 0

using namespace std;

vector<int> x, y, c, state, order;
vector<array<int, 2>> in;
int t = 0;

int tree(vector<int> nodes){
    // nodes.size() must be a power of 2
    // returns id of exit node
    while(nodes.size()>1){
        vector<int> nnodes;
        for(int i=0; i<nodes.size(); i+=2){
            x.push_back(nodes[i]);
            y.push_back(nodes[i+1]);
            state.push_back(0);

            nnodes.push_back(-x.size());
            if(nodes[i]>=0){
                in[nodes[i]]={-int(x.size()), 0};
            }
            if(nodes[i+1]>=0){
                in[nodes[i+1]]={-int(x.size()), 1};
            }
        }
        swap(nodes, nnodes);
    }
    return nodes.front();
}

void sim(int u){
    if(u>=0){
        if(order[u]!=-1){
            return;
        }
        order[u]=t++;
        sim(c[u]);
    }else{
        u = -u-1;
        if(state[u]==0){
            state[u]^=1;
            sim(x[u]);
        }else{
            state[u]^=1;
            sim(y[u]);
        }
    }
}

void create_circuit(int M, std::vector<int> A) {
    int n = A.size(), now = 1;
    vector<int> roots(20);
    in.assign(n+1, {});
    for(int i=0; i<20; i++){
        if(n&(1<<i)){
            vector<int> nodes(1<<i);
            iota(nodes.begin(), nodes.end(), now);
            roots[i]=tree(nodes);
            now += 1<<i;
        }
    }


    // make switcher
    int len = log2(n) + 1;
    int start = -x.size()-1;
    for(int i=0; i<len; i++){
        if(roots[len - i - 1]){
            x.push_back(roots[len - i - 1]);
            y.push_back(-x.size() - 1);
            state.push_back(0);
            if(roots[len - i - 1]>=0){
                in[roots[len - i - 1]] = {-int(x.size()), 0};
            }
        }else{
            x.push_back(start);
            y.push_back(-x.size() - 1);
            state.push_back(0);
     
        }
    }
    y.back() = 0;

    c.assign(n+1, start);
    order.assign(n+1, -1);

    sim(start);

    c.assign(M+1, start);
    c[0]=start;

    vector<array<int, 2>> rev(n+1);
    for(int i=0; i<order.size(); i++){
        rev[order[i]] = in[i];
    }
    debug(order);
    debug(c);
    debug(x);
    debug(y);
    debug(in);
    debug(rev);

    for(int i=0; i<n; i++){
        auto [module, side] = rev[i];
        module = -module - 1;
        if(side==0){
            x[module] = A[i];
        }else{
            y[module] = A[i];
        }
    }

    debug(c);
    debug(x);
    debug(y);

    answer(c, x, y);
}

Compilation message

doll.cpp: In function 'int tree(std::vector<int>)':
doll.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int i=0; i<nodes.size(); i+=2){
      |                      ~^~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i=0; i<order.size(); i++){
      |                  ~^~~~~~~~~~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:101:5: note: in expansion of macro 'debug'
  101 |     debug(order);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:102:5: note: in expansion of macro 'debug'
  102 |     debug(c);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:103:5: note: in expansion of macro 'debug'
  103 |     debug(x);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:104:5: note: in expansion of macro 'debug'
  104 |     debug(y);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:105:5: note: in expansion of macro 'debug'
  105 |     debug(in);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:106:5: note: in expansion of macro 'debug'
  106 |     debug(rev);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:118:5: note: in expansion of macro 'debug'
  118 |     debug(c);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:119:5: note: in expansion of macro 'debug'
  119 |     debug(x);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:120:5: note: in expansion of macro 'debug'
  120 |     debug(y);
      |     ^~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 26 ms 5960 KB Output is correct
3 Correct 25 ms 5444 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 43 ms 7176 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 26 ms 5960 KB Output is correct
3 Correct 25 ms 5444 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 43 ms 7176 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 50 ms 9680 KB Output is correct
9 Correct 54 ms 10404 KB Output is correct
10 Correct 91 ms 12872 KB Output is correct
11 Correct 0 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 26 ms 5960 KB Output is correct
3 Correct 25 ms 5444 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 43 ms 7176 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 50 ms 9680 KB Output is correct
9 Correct 54 ms 10404 KB Output is correct
10 Correct 91 ms 12872 KB Output is correct
11 Correct 0 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 82 ms 12540 KB Output is correct
15 Correct 55 ms 8608 KB Output is correct
16 Correct 81 ms 12540 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 82 ms 12800 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 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 420 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 46 ms 9340 KB Output is correct
3 Correct 45 ms 9348 KB Output is correct
4 Correct 91 ms 14080 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 46 ms 9340 KB Output is correct
3 Correct 45 ms 9348 KB Output is correct
4 Correct 91 ms 14080 KB Output is correct
5 Correct 81 ms 14080 KB Output is correct
6 Correct 81 ms 14096 KB Output is correct
7 Correct 79 ms 14080 KB Output is correct
8 Correct 81 ms 14076 KB Output is correct
9 Correct 52 ms 8872 KB Output is correct
10 Correct 79 ms 14084 KB Output is correct
11 Correct 77 ms 14084 KB Output is correct
12 Correct 46 ms 9396 KB Output is correct
13 Correct 46 ms 9896 KB Output is correct
14 Correct 48 ms 9892 KB Output is correct
15 Correct 47 ms 10084 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 52 ms 9240 KB Output is correct
18 Correct 53 ms 9612 KB Output is correct
19 Correct 46 ms 9396 KB Output is correct
20 Correct 78 ms 14180 KB Output is correct
21 Correct 79 ms 14076 KB Output is correct
22 Correct 79 ms 14080 KB Output is correct