이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<ll> vl;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
using namespace std;
void create_circuit(int m, vi a) { // example circuit
// m is the number of triggers
// n is the length of the sequence
int n = sz(a);
vi c(m + 1);
if (n == 1) {
f1r(i, 1, m + 1) {
c[i] = 0;
}
c[0] = a[0];
answer(c, vi(), vi());
return;
}
// root switch at -1
f1r(i, 1, m + 1) {
c[i] = -1; // connect to the root
}
c[0] = a[0];
a.erase(a.begin()); // erase first element
a.pb(0); // add the beginning again
// now from the root, we go to each number in some order
// we need n exits
// i -> 2 * i, 2 * i + 1
int d = 0;
while ((1 << d) < n) d++;
int sz = (1 << d); // this is the bottom row
// leaf nodes are the exits
int excess = sz - n; // stuff not used on bottom row
vi dead(2 * sz);
vi state(2 * sz);
f0r(i, excess) {
dead[sz + i] = 1;
}
function<void(int)> gather = [&](int u) {
if (u >= sz) return;
gather(2 * u);
gather(2 * u + 1);
dead[u] = (dead[2 * u] & dead[2 * u + 1]);
}; gather(1);
vi ord;
f0r(i, n) { // go through each of the nodes
int bot = -1;
function<bool(int)> go = [&](int u) -> bool {
if (u >= sz) {
bot = u;
return dead[u];
} else {
if (state[u] == 0) {
state[u] ^= 1;
return go(2 * u);
} else {
state[u] ^= 1;
return go(2 * u + 1);
}
}
}; while (go(1)) {}
ord.pb(bot);
}
map<int, int> xdest, ydest;
f0r(i, sz(ord)) {
int u = ord[i];
int p = u / 2;
if (2 * p == u) {
xdest[p] = a[i];
} else {
ydest[p] = a[i];
}
}
vi used;
function<void(int)> dfs = [&](int u) {
if (dead[u]) {
return;
}
if (u >= sz) {
return;
} else {
used.pb(u);
dfs(2 * u);
dfs(2 * u + 1);
}
};
dfs(1);
// cout << sz(used) << endl;
auto get_pos = [&](int x) -> int { return lower_bound(all(used), x) - used.begin(); };
int s = sz(used);
vi x(s);
vi y(s);
each(v, used) {
int i = get_pos(v);
if (2 * v < sz) {
if (!dead[2 * v]) {
int to = get_pos(2 * v);
x[i] = -(to + 1);
} else {
x[i] = -1;
}
if (!dead[2 * v + 1]) {
int to = get_pos(2 * v + 1);
y[i] = -(to + 1);
} else {
y[i] = -1;
}
} else {
if (!dead[2 * v]) {
x[i] = xdest[v];
} else {
x[i] = -1;
}
if (!dead[2 * v + 1]) {
y[i] = ydest[v];
} else {
y[i] = -1;
}
}
}
answer(c, x, y);
auto output = [&](vi v) { each(x, v) cout << x << " "; cout << endl; };
// output(c);
// output(x);
// output(y);
return;
}
/**
* n + log2 switches for full credit
* 1e5 triggers, 2e5 length sequence
* P is like 20 * n, which is like log2(m) * n ish?
* general observations
* from a trigger you go to same switch every time
* so you have a binary choice of next switch
* 2n switches is easy
* you can choose specifically which switches to ignore
* if you make it into like sets of 2^k, and then just redirect them back to the beginning
* the idea is you can figure out where to direct the things, i see
* subtask 1
* make a ordered cycle
* subtask 2
* if you go to some place twice, use the switch appropriately
* subtask 3
* you can just do similarly to task 2
* subtask 4
*
* subtask 5
*
* subtask 6
*
*/
컴파일 시 표준 에러 (stderr) 메시지
doll.cpp: In function 'void create_circuit(int, vi)':
doll.cpp:149:10: warning: variable 'output' set but not used [-Wunused-but-set-variable]
149 | auto output = [&](vi v) { each(x, v) cout << x << " "; cout << endl; };
| ^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |