oj.uz

답안 #643068

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
643068 2022-09-21T06:17:14 Z ghostwriter 자동 인형 (IOI18_doll) C++14
37 / 100
 202 ms 15468 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 {
    const int MAXS = 4e5 + 5;
    int M, N, S = 0, d[MAXS], d1[MAXS];
    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 - ((l + r) % 2 == 0? 1 : 0);
        vi left = build(l, mid);
        vi right = build(mid + 1, r);
        int root = --S;
        FOR(i, 1, sz(left) - 1) {
            int u = left[i], &x = X[-u - 1], &y = Y[-u - 1];
            if (x == left[0]) x = root;
            if (y == left[0]) y = root;
        }
        FOR(i, 1, sz(right) - 1) {
            int u = right[i], &x = X[-u - 1], &y = Y[-u - 1];
            if (x == right[0]) x = root;
            if (y == right[0]) y = root;
        }
        if (sz(left) < sz(right)) {
            if (sz(left) == 1) {
                int u = left[0];
                --S;
                add(S, u, root);
                left = {S, S};
            }
            else {
                vi nleft = {left[0]};
                FOR(i, 1, sz(left) - 1) {
                    int u = left[i];
                    int x = X[-u - 1], y = Y[-u - 1];
                    add(u, S - 1, S - 2);
                    nleft.pb(S - 1);
                    nleft.pb(S - 2);
                    --S;
                    add(S, x, root);
                    --S;
                    add(S, y, root);
                }
                swap(left, nleft);
            }
        }
        add(root, left[0], right[0]);
        vi ans = {root};
        FOR(i, 1, sz(left) - 1) ans.pb(left[i]);
        FOR(i, 1, sz(right) - 1) ans.pb(right[i]);
        if (sz(left) == 1) ans.pb(root);
        return ans;
    }
    void create_circuit(int M, vi A) {
        A.pb(0);
        N = sz(A);
        subtask456::M = M;
        subtask456::A = A;
        vi ans = build(0, N - 1);
        int root = ans[0];
        vi C(M + 1);
        FOR(i, 0, M) C[i] = root;
        int cur = 0, cnt = 0;
        WHILE(cnt < N) {
            int pre = cur;
            if (cur >= 0) cur = C[cur];
            else if (!d[-cur - 1]) {
                d[-cur - 1] ^= 1;
                cur = X[-cur - 1];
            }
            else {
                d[-cur - 1] ^= 1;
                cur = Y[-cur - 1];
            }
            if (cur >= 0) {
                cur = A[cnt];
                if (d[-pre - 1]) X[-pre - 1] = A[cnt++];
                else Y[-pre - 1] = A[cnt++];
            }
        }
        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);
}
/*
3 5
5 5 1 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:106:9: note: in expansion of macro 'FOR'
  106 |         FOR(i, 1, sz(left) - 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:111:9: note: in expansion of macro 'FOR'
  111 |         FOR(i, 1, sz(right) - 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:125:17: note: in expansion of macro 'FOR'
  125 |                 FOR(i, 1, sz(left) - 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:141:9: note: in expansion of macro 'FOR'
  141 |         FOR(i, 1, sz(left) - 1) ans.pb(left[i]);
      |         ^~~
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:142:9: note: in expansion of macro 'FOR'
  142 |         FOR(i, 1, sz(right) - 1) ans.pb(right[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:154:9: note: in expansion of macro 'FOR'
  154 |         FOR(i, 0, M) 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:179:5: note: in expansion of macro 'FOR'
  179 |     FOR(i, 0, N - 1) {
      |     ^~~
doll.cpp:178:10: warning: variable 'sub123' set but not used [-Wunused-but-set-variable]
  178 |     bool sub123 = 1;
      |          ^~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 2644 KB Output is partially correct
2 Partially correct 142 ms 13500 KB Output is partially correct
3 Partially correct 137 ms 12996 KB Output is partially correct
4 Partially correct 148 ms 14524 KB Output is partially correct

Subtask #6
28.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 2644 KB Output is partially correct
2 Partially correct 142 ms 13500 KB Output is partially correct
3 Partially correct 137 ms 12996 KB Output is partially correct
4 Partially correct 148 ms 14524 KB Output is partially correct
5 Partially correct 202 ms 15468 KB Output is partially correct
6 Partially correct 155 ms 15284 KB Output is partially correct
7 Partially correct 159 ms 15308 KB Output is partially correct
8 Partially correct 156 ms 14976 KB Output is partially correct
9 Partially correct 136 ms 13016 KB Output is partially correct
10 Partially correct 168 ms 14880 KB Output is partially correct
11 Partially correct 151 ms 14648 KB Output is partially correct
12 Partially correct 149 ms 12996 KB Output is partially correct
13 Partially correct 137 ms 13736 KB Output is partially correct
14 Partially correct 142 ms 13488 KB Output is partially correct
15 Partially correct 155 ms 13680 KB Output is partially correct
16 Partially correct 4 ms 3028 KB Output is partially correct
17 Correct 75 ms 9720 KB Output is correct
18 Partially correct 140 ms 13428 KB Output is partially correct
19 Partially correct 134 ms 13088 KB Output is partially correct
20 Partially correct 165 ms 14788 KB Output is partially correct
21 Partially correct 145 ms 14608 KB Output is partially correct
22 Partially correct 150 ms 14664 KB Output is partially correct