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 <bits/stdc++.h>
#include "doll.h"
using namespace std;
using ll = long long;
constexpr ll INF = 1000000000;
ll conn;
set<ll> st;
ll nxt = -2;
void connect(ll x, vector<int> &X, vector<int> &Y, ll idx) {
// cout << x << '\n';
if (X[idx] == 0) {
X[idx] = x;
}
else {
Y[idx] = x;
}
}
void distribute(ll sz, vector<int> &X, vector<int> &Y, vector<int> &A, ll idx) {
// cout << idx << ' ' << sz << ' ' << ex << endl;
if (idx >= X.size()) {
X.resize(idx + 1);
}
if (idx >= Y.size()) {
Y.resize(idx + 1);
}
// cout << sz << ' ' << e << '\n';
X[idx] = 0;
Y[idx] = 0;
if (sz == 2) {
connect(INF, X, Y, idx);
connect(INF, X, Y, idx);
return;
}
X[idx] = nxt;
nxt--;
Y[idx] = nxt;
nxt--;
distribute(sz - sz / 2, X, Y, A, -X[idx] - 1);
distribute(sz / 2, X, Y, A, -Y[idx] - 1);
}
void create_circuit(int M, vector<int> A) {
ll NN = A.size();
A.push_back(-1);
ll N = A.size();
ll y = 0;
ll ex = 1;
while (ex < N) {
ex *= 2;
}
while (A.size() < ex) {
A.push_back(-1);
}
N = A.size();
A[N - 1] = 0;
vector<int> C, X, Y;
C.push_back(-1);
for (int i = 0; i < M; i++) {
C.push_back(-1);
}
distribute(N, X, Y, A, 0);
// for (int i = 0; i < C.size(); i++) {
// cout << C[i] << '\n';
// }
// cout << conn << '\n';
while (!st.empty()) {
ll x = *st.begin();
st.erase(x);
Y[conn] = -x - 1;
conn = x;
}
ll pos = 0, cnt = 0;
vector<bool> state(X.size());
// for (int i = 0; i < X.size(); i++) {
// cout << X[i] << ' ' << Y[i] << endl;
// }
do {
// cout << pos << endl;
if (pos >= 0) {
pos = C[pos];
}
else {
// cout << '\t' << state[-pos - 1] << endl;
if (state[-pos - 1] == 0) {
if (X[-pos - 1] == INF) {
X[-pos - 1] = A[cnt++];
}
state[-pos - 1] = !state[-pos - 1];
pos = X[-pos - 1];
}
else {
if (Y[-pos - 1] == INF) {
Y[-pos - 1] = A[cnt++];
}
state[-pos - 1] = !state[-pos - 1];
pos = Y[-pos - 1];
}
}
} while (pos != 0);
// for (int i = 0; i < X.size(); i++) {
// cout << '\t' << X[i] << ' ' << Y[i] << endl;
// }
assert(X.size() <= NN * 2);
answer(C, X, Y);
}
Compilation message (stderr)
doll.cpp: In function 'void distribute(ll, std::vector<int>&, std::vector<int>&, std::vector<int>&, ll)':
doll.cpp:25:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | if (idx >= X.size()) {
| ~~~~^~~~~~~~~~~
doll.cpp:28:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | if (idx >= Y.size()) {
| ~~~~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:56:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
56 | while (A.size() < ex) {
| ~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from doll.cpp:1:
doll.cpp:108:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
108 | assert(X.size() <= NN * 2);
| ~~~~~~~~~^~~~~~~~~
doll.cpp:51:8: warning: unused variable 'y' [-Wunused-variable]
51 | ll y = 0;
| ^
# | 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... |