oj.uz

Submission #119638

# Submission time Handle Problem Language Result Execution time Memory
119638 2019-06-21T14:11:39 Z alexandra_udristoiu Mechanical Doll (IOI18_doll) C++14
100 / 100
 198 ms 13292 KB 
#include<iostream>
#include<vector>
#define DIM 200005
#include "doll.h"
using namespace std;
static int nr, k;
static vector<int> xsol, ysol, c;
static int w[DIM], st[DIM], v[DIM][2], pt[20];
static void solve(int nod, int niv, int n){
    if(n == 0 || niv == 1){
        return;
    }
    if(n <= pt[niv - 1]){
        v[nod][1] = ++k;
        solve(v[nod][1], niv - 1, n);
    }
    else{
        v[nod][1] = ++k;
        solve(v[nod][1], niv - 1, pt[niv - 1]);
        v[nod][0] = ++k;
        solve(v[nod][0], niv - 1, n - pt[niv - 1]);
    }
}
static void drum(int nod, int niv){
    if(nod == 0){
        return;
    }
    if(niv == 1){
        w[++nr] = nod;
        return;
    }
    drum(v[nod][ st[nod] ], niv - 1);
    st[nod] = 1 - st[nod];
}
void create_circuit(int m, vector<int> a){
    int n, i, j, p;
    n = a.size();
    a.push_back(0);
    pt[0] = 1;
    for(i = 1; ; i++){
        pt[i] = 2 * pt[i - 1];
        if(pt[i] >= n){
            p = i;
            break;
        }
    }
    k = 1;
    solve(1, p, n);
    nr = 0;
    for(i = 1; i <= pt[p]; i++){
        drum(1, p);
    }
    for(i = 1; i <= k; i++){
        v[i][0] = -v[i][0];
        v[i][1] = -v[i][1];
    }
    if(nr == n){
        for(i = 1; i <= n; i++){
            if(v[ w[i] ][0] == 0){
                v[ w[i] ][0] = a[i];
            }
            else{
                v[ w[i] ][1] = a[i];
            }
        }
    }
    else{
        v[ w[1] ][0] = -1;
        for(i = 2; i <= nr; i++){
            if(v[ w[i] ][0] == 0){
                v[ w[i] ][0] = a[i - 1];
            }
            else{
                v[ w[i] ][1] = a[i - 1];
            }
        }
    }
    for(i = 1; i <= k; i++){
        if(v[i][0] == 0){
            v[i][0] = -1;
        }
        if(v[i][1] == 0){
            v[i][1] = -1;
        }
    }
    v[ w[nr] ][1] = 0;
    for(i = 1; i <= k; i++){
        xsol.push_back(v[i][0]);
        ysol.push_back(v[i][1]);
    }
    c.push_back(a[0]);
    for(i = 1; i <= m; i++){
        c.push_back(-1);
    }
    answer(c, xsol, ysol);
    return;
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:36:15: warning: unused variable 'j' [-Wunused-variable]
   36 |     int n, i, j, p;
      |               ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 58 ms 5112 KB Output is correct
3 Correct 54 ms 5108 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 79 ms 7372 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 2 ms 204 KB Output is correct
2 Correct 58 ms 5112 KB Output is correct
3 Correct 54 ms 5108 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 79 ms 7372 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 98 ms 8644 KB Output is correct
9 Correct 109 ms 9220 KB Output is correct
10 Correct 198 ms 13292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 224 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 2 ms 204 KB Output is correct
2 Correct 58 ms 5112 KB Output is correct
3 Correct 54 ms 5108 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 79 ms 7372 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 98 ms 8644 KB Output is correct
9 Correct 109 ms 9220 KB Output is correct
10 Correct 198 ms 13292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 224 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 149 ms 12968 KB Output is correct
15 Correct 109 ms 8168 KB Output is correct
16 Correct 150 ms 12320 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 152 ms 13148 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 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 204 KB Output is correct
2 Correct 83 ms 7488 KB Output is correct
3 Correct 100 ms 7144 KB Output is correct
4 Correct 183 ms 10824 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 83 ms 7488 KB Output is correct
3 Correct 100 ms 7144 KB Output is correct
4 Correct 183 ms 10824 KB Output is correct
5 Correct 146 ms 12312 KB Output is correct
6 Correct 146 ms 11812 KB Output is correct
7 Correct 152 ms 11996 KB Output is correct
8 Correct 151 ms 11540 KB Output is correct
9 Correct 94 ms 7156 KB Output is correct
10 Correct 151 ms 11512 KB Output is correct
11 Correct 151 ms 11176 KB Output is correct
12 Correct 92 ms 7368 KB Output is correct
13 Correct 92 ms 7908 KB Output is correct
14 Correct 97 ms 7912 KB Output is correct
15 Correct 107 ms 8020 KB Output is correct
16 Correct 4 ms 460 KB Output is correct
17 Correct 86 ms 7740 KB Output is correct
18 Correct 87 ms 7592 KB Output is correct
19 Correct 95 ms 7396 KB Output is correct
20 Correct 140 ms 11300 KB Output is correct
21 Correct 153 ms 11088 KB Output is correct
22 Correct 142 ms 11112 KB Output is correct