oj.uz

Submission #558415

# Submission time Handle Problem Language Result Execution time Memory
558415 2022-05-07T09:25:10 Z maomao90 Mechanical Doll (IOI18_doll) C++17
100 / 100
 134 ms 12908 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;
#include "doll.h"

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005

int n, m;
vi a;
int x[MAXN * 2], y[MAXN * 2];
int tog[MAXN * 2];
int lg;

int ptr = 1;
int dnc(int lo, int hi, int k, int n) {
    if (lo == hi) return INF;
    int u = ptr++;
    int mid = lo + hi >> 1;
    if (n >> k & 1 ^ 1) {
        x[u] = -1;
        y[u] = -dnc(mid + 1, hi, k - 1, n);
    } else {
        x[u] = -dnc(lo, mid, k - 1, n);
        y[u] = -dnc(mid + 1, hi, k - 1, (1 << lg) - 1);
    }
    cerr << u << ": " << x[u] << ' ' << y[u] << '\n';
    return u;
}
void sim(int u, int t) {
    tog[u] ^= 1;
    if (tog[u] == 1) {
        if (x[u] == -INF) {
            x[u] = t;
        } else {
            sim(-x[u], t);
        }
    } else {
        if (y[u] == -INF) {
            y[u] = t;
        } else {
            sim(-y[u], t);
        }
    }
}

void create_circuit(int M, vi A) {
    a = A;
    n = A.size();
    m = M;
    a.pb(0);
    vi c(m + 1);
    c[0] = a[0];
    REP (i, 1, m + 1) {
        c[i] = -1;
    }
    if (n == 1) {
        REP (i, 1, m + 1) {
            c[i] = 0;
        }
        vi rx, ry;
        answer(c, rx, ry);
        return;
    }
    lg = 0;
    while ((1 << lg) < n) {
        lg++;
    }
    dnc(0, (1 << lg) - 1, lg - 1, n - 1);
    REP (i, 0, n) {
        sim(1, a[i + 1]);
    }
    vi rx, ry;
    REP (i, 1, ptr) {
        assert(x[i] != -INF && y[i] != -INF);
        rx.pb(x[i]);
        ry.pb(y[i]);
    }
    answer(c, rx, ry);
}

Compilation message

doll.cpp: In function 'int dnc(int, int, int, int)':
doll.cpp:48:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
doll.cpp:49:16: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   49 |     if (n >> k & 1 ^ 1) {
      |         ~~~~~~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 38 ms 4880 KB Output is correct
3 Correct 36 ms 5052 KB Output is correct
4 Correct 1 ms 232 KB Output is correct
5 Correct 9 ms 1492 KB Output is correct
6 Correct 55 ms 7196 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 38 ms 4880 KB Output is correct
3 Correct 36 ms 5052 KB Output is correct
4 Correct 1 ms 232 KB Output is correct
5 Correct 9 ms 1492 KB Output is correct
6 Correct 55 ms 7196 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 84 ms 9604 KB Output is correct
9 Correct 74 ms 9040 KB Output is correct
10 Correct 108 ms 12908 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 312 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 38 ms 4880 KB Output is correct
3 Correct 36 ms 5052 KB Output is correct
4 Correct 1 ms 232 KB Output is correct
5 Correct 9 ms 1492 KB Output is correct
6 Correct 55 ms 7196 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 84 ms 9604 KB Output is correct
9 Correct 74 ms 9040 KB Output is correct
10 Correct 108 ms 12908 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 108 ms 12424 KB Output is correct
15 Correct 68 ms 8044 KB Output is correct
16 Correct 106 ms 12220 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 308 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 106 ms 12596 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 308 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 61 ms 7600 KB Output is correct
3 Correct 63 ms 6628 KB Output is correct
4 Correct 93 ms 9912 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 61 ms 7600 KB Output is correct
3 Correct 63 ms 6628 KB Output is correct
4 Correct 93 ms 9912 KB Output is correct
5 Correct 128 ms 10876 KB Output is correct
6 Correct 98 ms 10504 KB Output is correct
7 Correct 127 ms 10608 KB Output is correct
8 Correct 100 ms 10248 KB Output is correct
9 Correct 60 ms 6704 KB Output is correct
10 Correct 100 ms 10212 KB Output is correct
11 Correct 95 ms 10044 KB Output is correct
12 Correct 63 ms 6660 KB Output is correct
13 Correct 73 ms 8128 KB Output is correct
14 Correct 72 ms 7020 KB Output is correct
15 Correct 64 ms 7172 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 64 ms 7972 KB Output is correct
18 Correct 66 ms 7856 KB Output is correct
19 Correct 67 ms 6636 KB Output is correct
20 Correct 98 ms 10000 KB Output is correct
21 Correct 134 ms 9928 KB Output is correct
22 Correct 95 ms 9912 KB Output is correct