oj.uz

Submission #396313

# Submission time Handle Problem Language Result Execution time Memory
396313 2021-04-29T17:54:24 Z 12tqian Mechanical Doll (IOI18_doll) C++17
100 / 100
 386 ms 22696 KB 
#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<ll> vl;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;

using namespace std;

void create_circuit(int m, vi a) { // example circuit
    // m is the number of triggers
    // n is the length of the sequence
    int n = sz(a);
    vi c(m + 1);
    if (n == 1) {
        f1r(i, 1, m + 1) {
            c[i] = 0;
        }
        c[0] = a[0];
        answer(c, vi(), vi());
        return;
    }
    // root switch at -1
    f1r(i, 1, m + 1) {
        c[i] = -1; // connect to the root
    }
    c[0] = a[0];
    a.erase(a.begin()); // erase first element
    a.pb(0); // add the beginning again 
    // now from the root, we go to each number in some order
    // we need n exits
    // i -> 2 * i, 2 * i + 1
    int d = 0;
    while ((1 << d) < n) d++;
    int sz = (1 << d); // this is the bottom row
    // leaf nodes are the exits
    int excess = sz - n; // stuff not used on bottom row
        
    vi dead(2 * sz);
    vi state(2 * sz);
    
    f0r(i, excess) {
        dead[sz + i] = 1;
    }
    
    function<void(int)> gather = [&](int u) {
        if (u >= sz) return;
        gather(2 * u);
        gather(2 * u + 1);
        dead[u] = (dead[2 * u] & dead[2 * u + 1]);
    }; gather(1); 

    vi ord;

    f0r(i, n) { // go through each of the nodes
        int bot = -1;
        function<bool(int)> go = [&](int u) -> bool {
            if (u >= sz) {
                bot = u;
                return dead[u];
            } else {
                if (state[u] == 0) {
                    state[u] ^= 1;
                    return go(2 * u); 
                } else {
                    state[u] ^= 1;
                    return go(2 * u + 1);
                }
            }
        }; while (go(1)) {}
        ord.pb(bot); 
    }
    map<int, int> xdest, ydest;
    f0r(i, sz(ord)) {
        int u = ord[i];
        int p = u / 2;
        if (2 * p == u) { 
            xdest[p] = a[i]; 
        } else {
            ydest[p] = a[i];
        }
    }
    vi used;
    function<void(int)> dfs = [&](int u) {
        if (dead[u]) {
            return;
        }
        if (u >= sz) {
            return;
        } else {
            used.pb(u);
            dfs(2 * u);
            dfs(2 * u + 1);
        }
    };
    dfs(1);
    // cout << sz(used) << endl;
    sort(all(used));
    auto get_pos = [&](int x) -> int { return lower_bound(all(used), x) - used.begin(); };
    int s = sz(used);
    vi x(s);    
    vi y(s);
    each(v, used) {
        int i = get_pos(v);
        if (2 * v < sz) {
            if (!dead[2 * v]) {
                int to = get_pos(2 * v);
                x[i] = -(to + 1);
            } else {
                x[i] = -1;
            }
            if (!dead[2 * v + 1]) {
                int to = get_pos(2 * v + 1);
                y[i] = -(to + 1);
            } else {
                y[i] = -1;
            }
        } else {
            if (!dead[2 * v]) {
                x[i] = xdest[v];
            } else {
                x[i] = -1;
            }
            if (!dead[2 * v + 1]) {
                y[i] = ydest[v];
            } else {
                y[i] = -1;
            }
        }
    }
    answer(c, x, y);
    auto output = [&](vi v) { each(x, v) cout << x << " "; cout << endl; };
#ifndef LOCAL
    // output(a);
    // output(c);
    // output(x);
    // output(y);
#endif
    return;
}

/**
 * n + log2 switches for full credit
 * 1e5 triggers, 2e5 length sequence
 * P  is like 20 * n, which is like log2(m) * n ish?
 * general observations
     * from a trigger you go to same switch every time
     * so you have a binary choice of next switch
     * 2n switches is easy
     * you can choose specifically which switches to ignore
     * if you make it into like sets of 2^k, and then just redirect them back to the beginning
     * the idea is you can figure out where to direct the things, i see
 * subtask 1
     * make a ordered cycle
 * subtask 2
     * if you go to some place twice, use the switch appropriately
 * subtask 3
     * you can just do similarly to task 2
 * subtask 4
     * 
 * subtask 5
     * 
 * subtask 6
     *
 */

Compilation message

doll.cpp: In function 'void create_circuit(int, vi)':
doll.cpp:150:10: warning: variable 'output' set but not used [-Wunused-but-set-variable]
  150 |     auto output = [&](vi v) { each(x, v) cout << x << " "; cout << endl; };
      |          ^~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 88 ms 8400 KB Output is correct
3 Correct 103 ms 8764 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 218 ms 12196 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 88 ms 8400 KB Output is correct
3 Correct 103 ms 8764 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 218 ms 12196 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 198 ms 14428 KB Output is correct
9 Correct 273 ms 16784 KB Output is correct
10 Correct 298 ms 22696 KB Output is correct
11 Correct 2 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 88 ms 8400 KB Output is correct
3 Correct 103 ms 8764 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 218 ms 12196 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 198 ms 14428 KB Output is correct
9 Correct 273 ms 16784 KB Output is correct
10 Correct 298 ms 22696 KB Output is correct
11 Correct 2 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 271 ms 22308 KB Output is correct
15 Correct 228 ms 16064 KB Output is correct
16 Correct 272 ms 22156 KB Output is correct
17 Correct 1 ms 284 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 301 ms 22588 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 2 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 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 156 ms 13776 KB Output is correct
3 Correct 207 ms 15676 KB Output is correct
4 Correct 252 ms 21708 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 156 ms 13776 KB Output is correct
3 Correct 207 ms 15676 KB Output is correct
4 Correct 252 ms 21708 KB Output is correct
5 Correct 284 ms 22084 KB Output is correct
6 Correct 273 ms 21836 KB Output is correct
7 Correct 260 ms 21944 KB Output is correct
8 Correct 285 ms 21696 KB Output is correct
9 Correct 218 ms 15784 KB Output is correct
10 Correct 287 ms 21732 KB Output is correct
11 Correct 298 ms 21712 KB Output is correct
12 Correct 220 ms 15632 KB Output is correct
13 Correct 179 ms 13832 KB Output is correct
14 Correct 252 ms 15936 KB Output is correct
15 Correct 216 ms 15924 KB Output is correct
16 Correct 6 ms 716 KB Output is correct
17 Correct 173 ms 13784 KB Output is correct
18 Correct 155 ms 13736 KB Output is correct
19 Correct 237 ms 15672 KB Output is correct
20 Correct 312 ms 21716 KB Output is correct
21 Correct 386 ms 21724 KB Output is correct
22 Correct 287 ms 21704 KB Output is correct