oj.uz

답안 #643069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
643069 2022-09-21T06:18:47 Z ghostwriter 자동 인형 (IOI18_doll) C++14
37 / 100
 168 ms 15520 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;
        }
        WHILE(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 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 2632 KB Output is partially correct
2 Partially correct 131 ms 13520 KB Output is partially correct
3 Partially correct 142 ms 13108 KB Output is partially correct
4 Partially correct 152 ms 14448 KB Output is partially correct

Subtask #6
28.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 2632 KB Output is partially correct
2 Partially correct 131 ms 13520 KB Output is partially correct
3 Partially correct 142 ms 13108 KB Output is partially correct
4 Partially correct 152 ms 14448 KB Output is partially correct
5 Partially correct 166 ms 15520 KB Output is partially correct
6 Partially correct 168 ms 15240 KB Output is partially correct
7 Partially correct 153 ms 15260 KB Output is partially correct
8 Partially correct 152 ms 14964 KB Output is partially correct
9 Partially correct 132 ms 13080 KB Output is partially correct
10 Partially correct 160 ms 14920 KB Output is partially correct
11 Partially correct 150 ms 14640 KB Output is partially correct
12 Partially correct 140 ms 13080 KB Output is partially correct
13 Partially correct 141 ms 13744 KB Output is partially correct
14 Partially correct 140 ms 13408 KB Output is partially correct
15 Partially correct 140 ms 13668 KB Output is partially correct
16 Partially correct 4 ms 3028 KB Output is partially correct
17 Correct 73 ms 9740 KB Output is correct
18 Partially correct 129 ms 13448 KB Output is partially correct
19 Partially correct 149 ms 12992 KB Output is partially correct
20 Partially correct 154 ms 14784 KB Output is partially correct
21 Partially correct 160 ms 14564 KB Output is partially correct
22 Partially correct 145 ms 14640 KB Output is partially correct