oj.uz

Submission #109440

# Submission time Handle Problem Language Result Execution time Memory
109440 2019-05-06T14:38:34 Z nvmdava Mechanical Doll (IOI18_doll) C++17
100 / 100
 173 ms 11116 KB 
//#include "doll.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int> C, X, Y, st;
int sz = 0;

void create_circuit(int M, std::vector<int> A);

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);

void solve(int id, int cnt, int dep){
    dep--;
    if(dep == 0){
        if(cnt == 1){
            X[-1-id] = -1;
            Y[-1-id] = 0;
        } else {
            X[-1-id] = 0;
            Y[-1-id] = 0;
        }
        return;
    }
    int l, r;
    r = min(1 << dep, cnt);
    l = cnt - r;
    X[-1-id] = -1;
    Y[-1-id] = -1;
    if(r){
        X.pb(0);
        Y.pb(0);
        st.pb(0);
        Y[-1-id] = --sz;
    }
    if(l){
        X.pb(0);
        Y.pb(0);
        st.pb(0);
        X[-1-id] = --sz;
    }
    if(r) solve(Y[-1-id], r, dep);
    if(l) solve(X[-1-id], l, dep);
}

void trav(int id, vector<int>& v, int t){
//    cerr<<id<<'\n';
    if(st[-1-id] == 0){
        st[-1-id] = 1;
        if(X[-1-id] == 0){
            X[-1-id] = v[t++];
            if(t == v.size()) return;
            trav(-1, v, t);
        } else
            trav(X[-1-id], v, t);
    } else {
        st[-1-id] = 0;
        if(Y[-1-id] == 0){
            Y[-1-id] = v[t++];
            if(t == v.size()) return;
            trav(-1, v, t);
        } else {
            trav(Y[-1-id], v, t);
        }
    }
}

void create_circuit(int M, vector<int> A) {
	C.resize(M + 1);
	--sz;
    for(int& x : C)
        x = -1;
    X.pb(0);
    Y.pb(0);
    st.pb(0);
    A.pb(0);
    solve(-1, A.size(), ceil(log2(A.size())));
    trav(-1, A, 0);
	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void trav(int, std::vector<int>&, int)':
doll.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if(t == v.size()) return;
      |                ~~^~~~~~~~~~~
doll.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             if(t == v.size()) return;
      |                ~~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 62 ms 4276 KB Output is correct
3 Correct 63 ms 4152 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1380 KB Output is correct
6 Correct 90 ms 6336 KB Output is correct
7 Correct 2 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 62 ms 4276 KB Output is correct
3 Correct 63 ms 4152 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1380 KB Output is correct
6 Correct 90 ms 6336 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 111 ms 6980 KB Output is correct
9 Correct 116 ms 7584 KB Output is correct
10 Correct 144 ms 11116 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 62 ms 4276 KB Output is correct
3 Correct 63 ms 4152 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1380 KB Output is correct
6 Correct 90 ms 6336 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 111 ms 6980 KB Output is correct
9 Correct 116 ms 7584 KB Output is correct
10 Correct 144 ms 11116 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 129 ms 10596 KB Output is correct
15 Correct 98 ms 6456 KB Output is correct
16 Correct 160 ms 10132 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 1 ms 252 KB Output is correct
20 Correct 153 ms 10836 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 2 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 94 ms 5568 KB Output is correct
3 Correct 111 ms 5564 KB Output is correct
4 Correct 127 ms 8868 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 94 ms 5568 KB Output is correct
3 Correct 111 ms 5564 KB Output is correct
4 Correct 127 ms 8868 KB Output is correct
5 Correct 153 ms 10004 KB Output is correct
6 Correct 144 ms 9784 KB Output is correct
7 Correct 161 ms 9736 KB Output is correct
8 Correct 173 ms 9512 KB Output is correct
9 Correct 121 ms 5568 KB Output is correct
10 Correct 131 ms 9532 KB Output is correct
11 Correct 134 ms 9224 KB Output is correct
12 Correct 92 ms 5820 KB Output is correct
13 Correct 103 ms 6180 KB Output is correct
14 Correct 95 ms 6268 KB Output is correct
15 Correct 106 ms 6440 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 80 ms 6308 KB Output is correct
18 Correct 100 ms 5764 KB Output is correct
19 Correct 99 ms 5792 KB Output is correct
20 Correct 134 ms 9464 KB Output is correct
21 Correct 141 ms 9236 KB Output is correct
22 Correct 129 ms 9312 KB Output is correct