This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "doll.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7;
void create_circuit(int m, vi a) {
a.PB(0);
int n = SZ(a);
vi x, y;
int sz = 0;
function<pair<int, V<pi>>(int, int)> dfs = [&] (int n, int m) -> pair<int, V<pi>> {
assert(n >= 1);
x.PB(0), y.PB(0);
int u = -(++sz);
V<pi> res;
if(m == 2) {
if(n == 1) res.EB(u, 0), res.EB(u, 3);
else res.EB(u, 0), res.EB(u, 1);
} else {
int rsz = min(n, m / 2);
int ul, ur;
V<pi> resl, resr;
tie(ur, resr) = dfs(rsz, m / 2);
y[-u - 1] = ur;
if(n - rsz) {
tie(ul, resl) = dfs(n - rsz, m / 2);
x[-u - 1] = ul;
} else {
for(int i = 0; i < m / 2; i++)
resl.EB(u, 2);
}
for(int i = 0; i < m / 2; i++) {
res.PB(resl[i]);
res.PB(resr[i]);
}
}
assert(SZ(res) == m);
return {u, res};
};
int mm = 1;
while(mm < n) mm *= 2;
auto [u, tt] = dfs(n, mm);
x.resize(sz), y.resize(sz);
int i = 0;
for(auto[who, tp]:tt) {
if(tp == 0) {
x[-who - 1] = a[i++];
} else if(tp == 1) {
y[-who - 1] = a[i++];
} else if(tp == 2) {
x[-who - 1] = u;
} else {
y[-who - 1] = u;
}
}
assert(i == n);
vi c(m + 1, u);
// for(int i = 0; i < SZ(x); i++)
// cerr << -(i + 1) << ": " << x[i] << " " << y[i] << endl;
answer(c, x, y);
}
Compilation message (stderr)
doll.cpp: In function 'void create_circuit(int, vi)':
doll.cpp:56:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
56 | auto [u, tt] = dfs(n, mm);
| ^
doll.cpp:59:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
59 | for(auto[who, tp]:tt) {
| ^
# | 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... |