# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
633329 | 2022-08-22T06:33:12 Z | ghostwriter | 동굴 (IOI13_cave) | C++14 | 954 ms | 672 KB |
#include "cave.h" #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include <debug.h> #include "grader.c" #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 Practising for VOI23 gold medal */ const int MAXN = 5000; int b[MAXN], s[MAXN], a[MAXN]; void exploreCave(int N) { memset(a, -1, sizeof a); FOR(i, 0, N - 1) { FOR(j, 0, N - 1) if (a[j] != -1) b[j] = s[j]; else b[j] = 0; int tmp = tryCombination(b), val = -1; if (tmp == -1 || tmp > i) val = 0; else val = 1; int l = 0, r = N - 1, ans = -1; WHILE(l <= r) { int mid = l + (r - l) / 2; FOR(j, 0, N - 1) if (a[j] != -1) b[j] = s[j]; else if (j <= mid) b[j] = val; else b[j] = val ^ 1; int tmp = tryCombination(b); if (tmp == -1 || tmp > i) { ans = mid; r = mid - 1; } else l = mid + 1; } s[ans] = val; a[ans] = i; } answer(s, a); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 357 ms | 460 KB | Output is correct |
2 | Correct | 367 ms | 672 KB | Output is correct |
3 | Correct | 548 ms | 432 KB | Output is correct |
4 | Correct | 364 ms | 424 KB | Output is correct |
5 | Correct | 554 ms | 436 KB | Output is correct |
6 | Correct | 547 ms | 548 KB | Output is correct |
7 | Correct | 552 ms | 556 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 534 ms | 436 KB | Output is correct |
13 | Correct | 544 ms | 440 KB | Output is correct |
14 | Correct | 561 ms | 440 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 563 ms | 524 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 499 ms | 436 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 308 KB | Output is correct |
6 | Correct | 555 ms | 436 KB | Output is correct |
7 | Correct | 444 ms | 420 KB | Output is correct |
8 | Correct | 912 ms | 436 KB | Output is correct |
9 | Correct | 940 ms | 432 KB | Output is correct |
10 | Correct | 954 ms | 452 KB | Output is correct |
11 | Correct | 470 ms | 556 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 312 KB | Output is correct |
3 | Correct | 0 ms | 312 KB | Output is correct |
4 | Correct | 1 ms | 308 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 308 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 0 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 312 KB | Output is correct |
3 | Correct | 0 ms | 312 KB | Output is correct |
4 | Correct | 1 ms | 308 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 308 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 0 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 1 ms | 340 KB | Output is correct |
17 | Correct | 1 ms | 316 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 1 ms | 312 KB | Output is correct |
20 | Correct | 70 ms | 340 KB | Output is correct |
21 | Correct | 1 ms | 308 KB | Output is correct |
22 | Correct | 1 ms | 340 KB | Output is correct |
23 | Correct | 110 ms | 376 KB | Output is correct |
24 | Correct | 111 ms | 376 KB | Output is correct |
25 | Correct | 111 ms | 384 KB | Output is correct |
26 | Correct | 1 ms | 340 KB | Output is correct |
27 | Correct | 1 ms | 340 KB | Output is correct |
28 | Correct | 82 ms | 376 KB | Output is correct |
29 | Correct | 1 ms | 340 KB | Output is correct |
30 | Correct | 58 ms | 376 KB | Output is correct |
31 | Correct | 57 ms | 340 KB | Output is correct |
32 | Correct | 1 ms | 312 KB | Output is correct |
33 | Correct | 1 ms | 340 KB | Output is correct |
34 | Correct | 1 ms | 340 KB | Output is correct |
35 | Correct | 112 ms | 376 KB | Output is correct |
36 | Correct | 137 ms | 340 KB | Output is correct |
37 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 357 ms | 460 KB | Output is correct |
2 | Correct | 367 ms | 672 KB | Output is correct |
3 | Correct | 548 ms | 432 KB | Output is correct |
4 | Correct | 364 ms | 424 KB | Output is correct |
5 | Correct | 554 ms | 436 KB | Output is correct |
6 | Correct | 547 ms | 548 KB | Output is correct |
7 | Correct | 552 ms | 556 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 534 ms | 436 KB | Output is correct |
13 | Correct | 544 ms | 440 KB | Output is correct |
14 | Correct | 561 ms | 440 KB | Output is correct |
15 | Correct | 563 ms | 524 KB | Output is correct |
16 | Correct | 0 ms | 340 KB | Output is correct |
17 | Correct | 499 ms | 436 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 1 ms | 308 KB | Output is correct |
20 | Correct | 555 ms | 436 KB | Output is correct |
21 | Correct | 444 ms | 420 KB | Output is correct |
22 | Correct | 912 ms | 436 KB | Output is correct |
23 | Correct | 940 ms | 432 KB | Output is correct |
24 | Correct | 954 ms | 452 KB | Output is correct |
25 | Correct | 470 ms | 556 KB | Output is correct |
26 | Correct | 1 ms | 340 KB | Output is correct |
27 | Correct | 1 ms | 312 KB | Output is correct |
28 | Correct | 0 ms | 312 KB | Output is correct |
29 | Correct | 1 ms | 308 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 1 ms | 340 KB | Output is correct |
33 | Correct | 1 ms | 340 KB | Output is correct |
34 | Correct | 1 ms | 308 KB | Output is correct |
35 | Correct | 1 ms | 340 KB | Output is correct |
36 | Correct | 1 ms | 340 KB | Output is correct |
37 | Correct | 1 ms | 340 KB | Output is correct |
38 | Correct | 1 ms | 340 KB | Output is correct |
39 | Correct | 0 ms | 340 KB | Output is correct |
40 | Correct | 1 ms | 340 KB | Output is correct |
41 | Correct | 1 ms | 340 KB | Output is correct |
42 | Correct | 1 ms | 316 KB | Output is correct |
43 | Correct | 1 ms | 340 KB | Output is correct |
44 | Correct | 1 ms | 312 KB | Output is correct |
45 | Correct | 70 ms | 340 KB | Output is correct |
46 | Correct | 1 ms | 308 KB | Output is correct |
47 | Correct | 1 ms | 340 KB | Output is correct |
48 | Correct | 110 ms | 376 KB | Output is correct |
49 | Correct | 111 ms | 376 KB | Output is correct |
50 | Correct | 111 ms | 384 KB | Output is correct |
51 | Correct | 1 ms | 340 KB | Output is correct |
52 | Correct | 1 ms | 340 KB | Output is correct |
53 | Correct | 82 ms | 376 KB | Output is correct |
54 | Correct | 1 ms | 340 KB | Output is correct |
55 | Correct | 58 ms | 376 KB | Output is correct |
56 | Correct | 57 ms | 340 KB | Output is correct |
57 | Correct | 1 ms | 312 KB | Output is correct |
58 | Correct | 1 ms | 340 KB | Output is correct |
59 | Correct | 1 ms | 340 KB | Output is correct |
60 | Correct | 112 ms | 376 KB | Output is correct |
61 | Correct | 137 ms | 340 KB | Output is correct |
62 | Correct | 1 ms | 340 KB | Output is correct |
63 | Correct | 349 ms | 548 KB | Output is correct |
64 | Correct | 401 ms | 448 KB | Output is correct |
65 | Correct | 567 ms | 556 KB | Output is correct |
66 | Correct | 363 ms | 416 KB | Output is correct |
67 | Correct | 547 ms | 552 KB | Output is correct |
68 | Correct | 530 ms | 564 KB | Output is correct |
69 | Correct | 528 ms | 436 KB | Output is correct |
70 | Correct | 0 ms | 340 KB | Output is correct |
71 | Correct | 0 ms | 340 KB | Output is correct |
72 | Correct | 550 ms | 436 KB | Output is correct |
73 | Correct | 526 ms | 440 KB | Output is correct |
74 | Correct | 538 ms | 556 KB | Output is correct |
75 | Correct | 506 ms | 436 KB | Output is correct |
76 | Correct | 1 ms | 340 KB | Output is correct |
77 | Correct | 1 ms | 340 KB | Output is correct |
78 | Correct | 551 ms | 440 KB | Output is correct |
79 | Correct | 437 ms | 440 KB | Output is correct |
80 | Correct | 951 ms | 436 KB | Output is correct |
81 | Correct | 904 ms | 460 KB | Output is correct |
82 | Correct | 906 ms | 436 KB | Output is correct |
83 | Correct | 437 ms | 428 KB | Output is correct |
84 | Correct | 1 ms | 340 KB | Output is correct |
85 | Correct | 63 ms | 392 KB | Output is correct |
86 | Correct | 390 ms | 420 KB | Output is correct |
87 | Correct | 1 ms | 340 KB | Output is correct |
88 | Correct | 1 ms | 308 KB | Output is correct |
89 | Correct | 110 ms | 340 KB | Output is correct |
90 | Correct | 109 ms | 460 KB | Output is correct |
91 | Correct | 108 ms | 340 KB | Output is correct |
92 | Correct | 880 ms | 440 KB | Output is correct |
93 | Correct | 865 ms | 448 KB | Output is correct |
94 | Correct | 871 ms | 432 KB | Output is correct |
95 | Correct | 1 ms | 312 KB | Output is correct |
96 | Correct | 1 ms | 340 KB | Output is correct |
97 | Correct | 473 ms | 548 KB | Output is correct |
98 | Correct | 82 ms | 380 KB | Output is correct |
99 | Correct | 532 ms | 432 KB | Output is correct |
100 | Correct | 1 ms | 340 KB | Output is correct |
101 | Correct | 57 ms | 324 KB | Output is correct |
102 | Correct | 57 ms | 372 KB | Output is correct |
103 | Correct | 383 ms | 420 KB | Output is correct |
104 | Correct | 1 ms | 340 KB | Output is correct |
105 | Correct | 1 ms | 340 KB | Output is correct |
106 | Correct | 1 ms | 340 KB | Output is correct |
107 | Correct | 112 ms | 376 KB | Output is correct |
108 | Correct | 108 ms | 372 KB | Output is correct |
109 | Correct | 889 ms | 436 KB | Output is correct |
110 | Correct | 892 ms | 432 KB | Output is correct |
111 | Correct | 1 ms | 316 KB | Output is correct |