oj.uz

Submission #288525

# Submission time Handle Problem Language Result Execution time Memory
288525 2020-09-01T15:05:20 Z andrew Mechanical Doll (IOI18_doll) C++17
37 / 100
 535 ms 22212 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), 0);
        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 3 ms 204 KB Output is partially correct
2 Partially correct 369 ms 20912 KB Output is partially correct
3 Partially correct 344 ms 20920 KB Output is partially correct
4 Partially correct 495 ms 21072 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 204 KB Output is partially correct
2 Partially correct 369 ms 20912 KB Output is partially correct
3 Partially correct 344 ms 20920 KB Output is partially correct
4 Partially correct 495 ms 21072 KB Output is partially correct
5 Partially correct 442 ms 22212 KB Output is partially correct
6 Partially correct 453 ms 22148 KB Output is partially correct
7 Partially correct 510 ms 22204 KB Output is partially correct
8 Partially correct 366 ms 21952 KB Output is partially correct
9 Partially correct 366 ms 20904 KB Output is partially correct
10 Partially correct 535 ms 21728 KB Output is partially correct
11 Partially correct 471 ms 21464 KB Output is partially correct
12 Partially correct 375 ms 21164 KB Output is partially correct
13 Partially correct 452 ms 21496 KB Output is partially correct
14 Partially correct 351 ms 21576 KB Output is partially correct
15 Partially correct 477 ms 21672 KB Output is partially correct
16 Partially correct 6 ms 972 KB Output is partially correct
17 Correct 151 ms 11704 KB Output is correct
18 Partially correct 448 ms 21120 KB Output is partially correct
19 Partially correct 335 ms 21156 KB Output is partially correct
20 Partially correct 359 ms 21664 KB Output is partially correct
21 Partially correct 439 ms 21388 KB Output is partially correct
22 Partially correct 350 ms 21520 KB Output is partially correct