oj.uz

Submission #642879

# Submission time Handle Problem Language Result Execution time Memory
642879 2022-09-20T17:23:29 Z ghostwriter Mechanical Doll (IOI18_doll) C++14
16 / 100
 86 ms 13260 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
const int MAXM = 1e5 + 5;
int d[MAXM];
namespace subtask123 {
    vi next[MAXM];
    void create_circuit(int M, vi A) {
        vi C(M + 1, 0), X, Y;
        int N = sz(A);
        next[0].pb(A[0]);
        FOR(i, 0, N - 1) next[A[i]].pb(i == N - 1? 0 : A[i + 1]);
        int S = 0;
        FOR(i, 0, M) {
            if (next[i].empty()) {
                C[i] = 0;
                continue;
            }
            if (sz(next[i]) == 1) {
                C[i] = next[i][0];
                continue;
            }
            if (sz(next[i]) == 2) {
                C[i] = --S;
                X.pb(next[i][0]);
                Y.pb(next[i][1]);
                continue;
            }
            if (sz(next[i]) == 3) {
                C[i] = --S;
                X.pb(S - 1);
                Y.pb(S - 2);
                --S;
                X.pb(next[i][0]);
                Y.pb(next[i][1]);
                --S;
                X.pb(S + 2);
                Y.pb(next[i][2]);
                continue;
            }
            C[i] = --S;
            X.pb(S - 1);
            Y.pb(S - 2);
            --S;
            X.pb(next[i][0]);
            Y.pb(next[i][2]);
            --S;
            X.pb(next[i][1]);
            Y.pb(next[i][3]);
        }
        answer(C, X, Y);
    }
}
namespace subtask456 {
    int M, N, S = 0;
    vi A, X, Y;
    void add(int u, int x, int y) {
        WHILE(-u - 1 >= sz(X)) {
            X.pb(0);
            Y.pb(0);
        }
        X[-u - 1] = x;
        Y[-u - 1] = y;
    }
    vi build(int l, int r) {
        if (l == r) return {A[l]};
        int mid = (l + r) / 2;
        vi left = build(l, mid);
        vi right = build(mid + 1, r);
        int root = --S;
        if (sz(left) > sz(right)) {
            if (sz(right) == 1) {
                int u = right[0];
                --S;
                add(S, u, root);
                right = {S, S};
            }
            else {
                vi nright = {right[0]};
                FOR(i, 1, sz(right) - 1) {
                    int u = right[i];
                    int x = X[-u - 1], y = Y[-u - 1];
                    add(u, S - 1, S - 2);
                    nright.pb(S - 1);
                    nright.pb(S - 2);
                    --S;
                    add(S, x, root);
                    --S;
                    add(S, y, root);
                }
                right = nright;
            }
        }
        add(root, left[0], right[0]);
        vi ans = {root};
        EACH(i, left) ans.pb(i);
        EACH(i, right) ans.pb(i);
        return ans;
    }
    void create_circuit(int M, vi A) {
        A.pb(0);
        N = sz(A);
        subtask456::M = M;
        subtask456::A = A;
        build(0, N - 1);
        vi ans = build(0, N - 1);
        int root = ans[0];
        vi C(M + 1);
        FOR(i, 0, M - 1) C[i] = root;
        answer(C, X, Y);
    }
}
void create_circuit(int M, std::vector<int> A) {
    int N = A.size();
    bool sub123 = 1;
    FOR(i, 0, N - 1) {
        ++d[A[i]];
        if (d[A[i]] > 4) sub123 = 0;
    }
    if (sub123) {
        subtask123::create_circuit(M, A);
        return;
    }
    subtask456::create_circuit(M, A);
}
/*
4 4
1 2 1 3
*/

Compilation message

doll.cpp: In function 'void subtask123::create_circuit(int, vi)':
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:46:9: note: in expansion of macro 'FOR'
   46 |         FOR(i, 0, N - 1) next[A[i]].pb(i == N - 1? 0 : A[i + 1]);
      |         ^~~
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:48:9: note: in expansion of macro 'FOR'
   48 |         FOR(i, 0, M) {
      |         ^~~
doll.cpp: In function 'vi subtask456::build(int, int)':
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:114:17: note: in expansion of macro 'FOR'
  114 |                 FOR(i, 1, sz(right) - 1) {
      |                 ^~~
doll.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
doll.cpp:130:9: note: in expansion of macro 'EACH'
  130 |         EACH(i, left) ans.pb(i);
      |         ^~~~
doll.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
doll.cpp:131:9: note: in expansion of macro 'EACH'
  131 |         EACH(i, right) ans.pb(i);
      |         ^~~~
doll.cpp: In function 'void subtask456::create_circuit(int, vi)':
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:143:9: note: in expansion of macro 'FOR'
  143 |         FOR(i, 0, M - 1) C[i] = root;
      |         ^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:150:5: note: in expansion of macro 'FOR'
  150 |     FOR(i, 0, N - 1) {
      |     ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 27 ms 7436 KB Output is correct
3 Correct 27 ms 6892 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 9 ms 3808 KB Output is correct
6 Correct 33 ms 8864 KB Output is correct
7 Correct 2 ms 2656 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 27 ms 7436 KB Output is correct
3 Correct 27 ms 6892 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 9 ms 3808 KB Output is correct
6 Correct 33 ms 8864 KB Output is correct
7 Correct 2 ms 2656 KB Output is correct
8 Correct 43 ms 9256 KB Output is correct
9 Correct 50 ms 9928 KB Output is correct
10 Correct 71 ms 12728 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2664 KB Output is correct
13 Correct 3 ms 2644 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 27 ms 7436 KB Output is correct
3 Correct 27 ms 6892 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 9 ms 3808 KB Output is correct
6 Correct 33 ms 8864 KB Output is correct
7 Correct 2 ms 2656 KB Output is correct
8 Correct 43 ms 9256 KB Output is correct
9 Correct 50 ms 9928 KB Output is correct
10 Correct 71 ms 12728 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2664 KB Output is correct
13 Correct 3 ms 2644 KB Output is correct
14 Correct 86 ms 13260 KB Output is correct
15 Correct 48 ms 8484 KB Output is correct
16 Correct 68 ms 11280 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 3 ms 2600 KB Output is correct
19 Correct 3 ms 2644 KB Output is correct
20 Correct 77 ms 12696 KB Output is correct
21 Correct 1 ms 2644 KB Output is correct
22 Correct 1 ms 2656 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -