답안 #80169 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
80169	2018-10-19T12:00:07 Z	wleung_bvg	자동 인형 (IOI18_doll)	C++14	100 / 100	135 ms	7852 KB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define all(a) (a).begin(),(a).end()
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define FOR(i,b) For(i,0,b)
#define Rev(i,a,b) for(auto i=(a);i>(b);i--)
#define REV(i,a) Rev(i,a,-1)
#define FORE(i,a) for(auto&&i:a)
#define sz(a) (int((a).size()))
#define MIN(a,b) ((a)=min((a),(b)))
#define MAX(a,b) ((a)=max((a),(b)))
using ll=long long;using ld=long double;using uint=unsigned int;using ull=unsigned long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pill=pair<int,ll>;using plli=pair<ll,int>;using pdd=pair<double,double>;using pld=pair<ld,ld>;
constexpr const char nl='\n',sp=' ';constexpr const int INT_INF=0x3f3f3f3f;constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f;
constexpr const double D_INF=numeric_limits<double>::infinity();constexpr const ld LD_INF=numeric_limits<ld>::infinity();constexpr const double EPS=1e-9;

const int MAXN = 2e5 + 5;

int N, H, cur = 1, X[MAXN * 2], Y[MAXN * 2];
bool T[MAXN * 2];

int build(int l, int r) {
    if (r <= H - N) return 1;
    if (l >= r) return 0;
    int m = l + (r - l) / 2, ret = cur++;
    T[ret] = false;
    X[ret] = build(l, m);
    Y[ret] = build(m + 1, r);
    return ret;
}

void create_circuit(int M, vector<int> A) {
    N = A.size();
    for (H = 1; H < N; H *= 2);
    build(1, H);
    for (int j, i = 1; i <= N; i++) {
        for (j = 1; ((T[j] ^= 1) ? X[j] : Y[j]) != 0; j = T[j] ? X[j] : Y[j]) assert(j > 0);
        (T[j] ? X[j] : Y[j]) = i == N ? 0 : -A[i];
    }
    For(i, 1, cur) {
        assert(!T[i]);
        X[i] = -X[i];
        Y[i] = -Y[i];
    }
    vector<int> C(M + 1, -(N != 1));
    C[0] = A[0];
    answer(C, vector<int>(X + 1, X + cur), vector<int>(Y + 1, Y + cur));
}

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	48 ms	3532 KB	Output is correct
3	Correct	45 ms	3200 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	12 ms	1484 KB	Output is correct
6	Correct	66 ms	4676 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	48 ms	3532 KB	Output is correct
3	Correct	45 ms	3200 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	12 ms	1484 KB	Output is correct
6	Correct	66 ms	4676 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	82 ms	5316 KB	Output is correct
9	Correct	91 ms	5688 KB	Output is correct
10	Correct	127 ms	7852 KB	Output is correct
11	Correct	1 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	48 ms	3532 KB	Output is correct
3	Correct	45 ms	3200 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	12 ms	1484 KB	Output is correct
6	Correct	66 ms	4676 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	82 ms	5316 KB	Output is correct
9	Correct	91 ms	5688 KB	Output is correct
10	Correct	127 ms	7852 KB	Output is correct
11	Correct	1 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	124 ms	7536 KB	Output is correct
15	Correct	76 ms	4916 KB	Output is correct
16	Correct	122 ms	7408 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	2 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	128 ms	7704 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct

Subtask #5
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	75 ms	4532 KB	Output is correct
3	Correct	73 ms	4544 KB	Output is correct
4	Correct	110 ms	6692 KB	Output is correct

Subtask #6
56.0 / 56.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	75 ms	4532 KB	Output is correct
3	Correct	73 ms	4544 KB	Output is correct
4	Correct	110 ms	6692 KB	Output is correct
5	Correct	117 ms	7308 KB	Output is correct
6	Correct	135 ms	7352 KB	Output is correct
7	Correct	132 ms	7420 KB	Output is correct
8	Correct	124 ms	7104 KB	Output is correct
9	Correct	70 ms	4528 KB	Output is correct
10	Correct	114 ms	6920 KB	Output is correct
11	Correct	118 ms	6724 KB	Output is correct
12	Correct	86 ms	4528 KB	Output is correct
13	Correct	73 ms	4772 KB	Output is correct
14	Correct	80 ms	4928 KB	Output is correct
15	Correct	79 ms	5012 KB	Output is correct
16	Correct	3 ms	460 KB	Output is correct
17	Correct	71 ms	4552 KB	Output is correct
18	Correct	73 ms	4532 KB	Output is correct
19	Correct	75 ms	4544 KB	Output is correct
20	Correct	124 ms	6776 KB	Output is correct
21	Correct	127 ms	6700 KB	Output is correct
22	Correct	111 ms	6684 KB	Output is correct

답안 #80169

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 4.0 / 4.0

Subtask #3 10.0 / 10.0

Subtask #4 10.0 / 10.0

Subtask #5 18.0 / 18.0

Subtask #6 56.0 / 56.0

Subtask #1
2.0 / 2.0

Subtask #2
4.0 / 4.0

Subtask #3
10.0 / 10.0

Subtask #4
10.0 / 10.0

Subtask #5
18.0 / 18.0

Subtask #6
56.0 / 56.0