oj.uz

Submission #288523

# Submission time Handle Problem Language Result Execution time Memory
288523 2020-09-01T15:04:30 Z andrew Mechanical Doll (IOI18_doll) C++17
37 / 100
 531 ms 22216 KB 
#include <bits/stdc++.h>
#include "doll.h"

#define fi first
#define se second
#define p_b push_back
#define m_p make_pair
#define sz(x) (int)x.size()
#define pii pair <int, int>
#define all(x) x.begin(),x.end()

using namespace std;
typedef long long ll;
const ll inf = 1e7;

ll stn = 0, id = -1, uk;

vector <int> x, y, st, l, r, idx, le, ri;

int build(int v, int tl, int tr){
    le[v] = tl;
    ri[v] = tr;
    if(tl == tr)return 0;
    else{
        int tm = (tl + tr) >> 1;
        int t = stn, d = id;
        idx[v] = t;
        stn++;
        id--;
        l[v] = sz(l);

        l.p_b(0);
        r.p_b(0);
        le.p_b(0);
        ri.p_b(0);

        x.p_b(0);
        y.p_b(0);

        idx.p_b(0);

        r[v] = sz(l);

        l.p_b(0);
        r.p_b(0);
        le.p_b(0);
        ri.p_b(0);

        idx.p_b(0);
        int vv = build(l[v], tl, tm);
        x[t] = vv;
        vv = build(r[v], tm + 1, tr);
        y[t] = vv;
        return d;
    }
}

int dfs(int v){
    if(le[v] == ri[v])return st[uk++];
    else{
        int t = idx[v];
        int V = dfs(l[v]);
        if(V != inf){
            x[t] = V;
        }
        swap(l[v], r[v]);
        swap(x[t], y[t]);
        return inf;
    }
}

void create_circuit(int M, vector<int> A) {
    int n = sz(A);
    stn = 0;
    id = -1;
    std::vector<int> C(M + 1);
    vector <vector <int>> v(M + 1);
    if(sz(A) == 1){
        fill(all(C), -1);
        C[0] = A[0];
        C[A[0]] = 0;
        answer(C, x, y);
        return;
    }

    while((sz(A) & (sz(A) + 1)))A.p_b(-1);
    A.p_b(0);

    st = A;
    fill(all(C), -1);
    l.clear();
    le.clear();
    r.clear();
    ri.clear();
    uk = 0;
    l.p_b(0);
    le.p_b(0);
    r.p_b(0);
    ri.p_b(0);
    idx.p_b(0);
    C[0] = build(0, 0, sz(st) - 1);
    uk = 0;
    for(int i = 0; i < sz(st); i++){
        dfs(0);
    }

    answer(C, x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:73:9: warning: unused variable 'n' [-Wunused-variable]
   73 |     int n = sz(A);
      |         ^

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Partially correct 409 ms 20924 KB Output is partially correct
3 Partially correct 354 ms 20920 KB Output is partially correct
4 Partially correct 513 ms 21124 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Partially correct 409 ms 20924 KB Output is partially correct
3 Partially correct 354 ms 20920 KB Output is partially correct
4 Partially correct 513 ms 21124 KB Output is partially correct
5 Partially correct 437 ms 22216 KB Output is partially correct
6 Partially correct 404 ms 22144 KB Output is partially correct
7 Partially correct 531 ms 22160 KB Output is partially correct
8 Partially correct 450 ms 21872 KB Output is partially correct
9 Partially correct 434 ms 20920 KB Output is partially correct
10 Partially correct 531 ms 21716 KB Output is partially correct
11 Partially correct 438 ms 21468 KB Output is partially correct
12 Partially correct 411 ms 21196 KB Output is partially correct
13 Partially correct 379 ms 21572 KB Output is partially correct
14 Partially correct 443 ms 21648 KB Output is partially correct
15 Partially correct 390 ms 21704 KB Output is partially correct
16 Partially correct 5 ms 972 KB Output is partially correct
17 Correct 114 ms 11668 KB Output is correct
18 Partially correct 345 ms 21284 KB Output is partially correct
19 Partially correct 451 ms 21060 KB Output is partially correct
20 Partially correct 442 ms 21800 KB Output is partially correct
21 Partially correct 451 ms 21456 KB Output is partially correct
22 Partially correct 449 ms 21440 KB Output is partially correct