oj.uz

Submission #137677

# Submission time Handle Problem Language Result Execution time Memory
137677 2019-07-28T08:28:05 Z bensonlzl Mechanical Doll (IOI18_doll) C++14
100 / 100
 289 ms 17832 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;

int mlevel;

int cnt = 1;
int pow2[25];
int bigN;
int sequence[200005];

vector<int> X, Y;

struct switcher{
    switcher *left = nullptr, *right = nullptr;
    int level, id, lnode, rnode, state = 0;
    switcher(int n, int lv, int offset){
        id = cnt;
        cnt++;
        if (lv == 0){
            if (n == 2){
                lnode = 1;
                rnode = 1;
            }
            else{
                lnode = 1;
                rnode = -1;
            }
        }
        else{
            if (n > pow2[lv]){
                left = new switcher(n-pow2[lv],lv-1,offset);
                right = new switcher(pow2[lv],lv-1,offset+n-pow2[lv]);
                lnode = -left->id;
                rnode = -right->id;
            }
            else{
                right = new switcher(n,lv-1,offset);
                lnode = -1;
                rnode = -right->id;
            }
            
        } 
    }
    void revisit(switcher *r){
        if (lnode == -1){
            left = r;
        }
        if (rnode == -1){
            right = r;
        }

        if (left != nullptr && left != r){
            left->revisit(r);
        }
        if (right != r && right != nullptr){
            right->revisit(r);
        }
    }
}*root;

void dfs(switcher *cur, int nx){
    if (nx > bigN) return;
    if (cur->state == 0){
        cur->state = 1;
        if (cur->left == nullptr){
            cur->lnode = sequence[nx];
            X[cur->id-1] = sequence[nx];
            dfs(root,nx+1);
        }
        else{
            X[cur->id-1] = -cur->left->id;
            dfs(cur->left,nx);
        }
    }
    else{
        cur->state = 0;
        if (cur->right == nullptr){
            cur->lnode = sequence[nx];
            Y[cur->id-1] = sequence[nx];
            dfs(root,nx+1);
        }
        else{
            Y[cur->id-1] = -cur->right->id;
            dfs(cur->right,nx);
        }
    }
}

void create_circuit(int M, vector<int> A) {
    int N = A.size();
    bigN = N;
    vector<int> C;
    C.resize(M+1);
    if (N == 1){
        C[0] = A[0];
        C[1] = 0;
        answer(C,X,Y);
        return;
    }
    pow2[0] = 1;
    for (int i = 1; i < 25; ++i){
        pow2[i] = pow2[i-1]*2;
    }
    C[0] = A[0];
    for (int i = 1; i <= M; ++i){
        C[i] = -1;
    }
    for (int i = 0; i < A.size(); ++i){
        if (i == A.size()-1){
            sequence[i+1] = 0;
        }
        else sequence[i+1] = A[i+1];
    }
    //cout << "YEET\n" << flush;
    int x = 1, p = 0;
    while (x < N){
        p++;
        x *= 2;
    }
    root = new switcher(N,p-1,1);
    //cout << "YEET\n" << flush;
    X.resize(cnt);
    Y.resize(cnt);
    //cout << "YEET\n" << flush;
    root->revisit(root);
    //cout << "YEET\n" << flush;
    switcher *a = root;
    //cout << "YEET\n" << flush;
    dfs(a,1);
    //cout << "YEET\n" << flush;
    answer(C, X, Y);
}

Compilation message

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 52 ms 6872 KB Output is correct
3 Correct 50 ms 6480 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 83 ms 9668 KB Output is correct
7 Correct 1 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 52 ms 6872 KB Output is correct
3 Correct 50 ms 6480 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 83 ms 9668 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 160 ms 11852 KB Output is correct
9 Correct 140 ms 12152 KB Output is correct
10 Correct 289 ms 17832 KB Output is correct
11 Correct 3 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 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 52 ms 6872 KB Output is correct
3 Correct 50 ms 6480 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 83 ms 9668 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 160 ms 11852 KB Output is correct
9 Correct 140 ms 12152 KB Output is correct
10 Correct 289 ms 17832 KB Output is correct
11 Correct 3 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 208 ms 17532 KB Output is correct
15 Correct 103 ms 11468 KB Output is correct
16 Correct 208 ms 17324 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 187 ms 17604 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 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 1 ms 280 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 2 ms 204 KB Output is correct
2 Correct 101 ms 11076 KB Output is correct
3 Correct 122 ms 11080 KB Output is correct
4 Correct 218 ms 16680 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 101 ms 11076 KB Output is correct
3 Correct 122 ms 11080 KB Output is correct
4 Correct 218 ms 16680 KB Output is correct
5 Correct 240 ms 17216 KB Output is correct
6 Correct 259 ms 17220 KB Output is correct
7 Correct 242 ms 17340 KB Output is correct
8 Correct 270 ms 17052 KB Output is correct
9 Correct 133 ms 11072 KB Output is correct
10 Correct 219 ms 16928 KB Output is correct
11 Correct 204 ms 16700 KB Output is correct
12 Correct 154 ms 11080 KB Output is correct
13 Correct 158 ms 11372 KB Output is correct
14 Correct 166 ms 11392 KB Output is correct
15 Correct 129 ms 11552 KB Output is correct
16 Correct 3 ms 608 KB Output is correct
17 Correct 124 ms 11104 KB Output is correct
18 Correct 133 ms 11076 KB Output is correct
19 Correct 161 ms 11084 KB Output is correct
20 Correct 212 ms 16796 KB Output is correct
21 Correct 205 ms 16676 KB Output is correct
22 Correct 233 ms 16676 KB Output is correct