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 rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
using namespace std;
using ll = long long;
template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
vector<vector<int>> B(M + 1);
rep (i, N) B[A[i]].push_back(i);
vector<int> C(M + 1);
C[0] = A[0];
int cur = 1;
int lst = -1;
vector<pair<int, int>> memo;
rep2 (i, 1, M + 1) {
if (B[i].empty()) {
C[i] = 0;
continue;
}
if (B[i].size() == 1) {
if (B[i][0] < N - 1) C[i] = A[B[i][0] + 1];
else lst = i;
continue;
}
int lev = 0;
while ((1 << lev) < B[i].size()) ++lev;
if ((1 << lev) != B[i].size()) {
memo.emplace_back(i, -1);
}
int r = 1;
auto dfs = [&](auto&& dfs, int v, vector<int> p, int lev, bool f) -> void {
if (lev == 0) {
if (p.empty()) {
if (f) memo.back().second = v;
else C[v] = r;
}
else {
assert(p.size() == 1);
if (p[0] < N - 1) C[v] = A[p[0] + 1];
else lst = v;
}
return;
}
vector<int> p0, p1;
rep (i, p.size()) {
if (i % 2 == 0) p0.push_back(p[i]);
else p1.push_back(p[i]);
}
int t = cur++;
if (r == 1) r = -t;
C.push_back(0); C.push_back(0);
C[v] = -t;
int tmp = C.size();
dfs(dfs, tmp - 2, p0, lev - 1, false);
dfs(dfs, tmp - 1, p1, lev - 1, f);
};
dfs(dfs, i, B[i], lev, true);
if ((1 << lev) != B[i].size()) memo.back().first = r;
}
{
if (memo.empty()) C[lst] = 0;
else {
C[lst] = memo[0].first;
rep (i, memo.size() - 1) {
C[memo[0].second] = memo[i + 1].first;
}
C[memo.back().second] = 0;
}
}
vector<int> X(cur - 1), Y(cur - 1);
rep (i, cur - 1) {
X[i] = C[M + 1 + i * 2];
Y[i] = C[M + 1 + i * 2 + 1];
}
C.resize(M + 1);
answer(C, X, Y);
}
Compilation message (stderr)
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:37:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | while ((1 << lev) < B[i].size()) ++lev;
| ~~~~~~~~~~~^~~~~~~~~~~~~
doll.cpp:38:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | if ((1 << lev) != B[i].size()) {
| ~~~~~~~~~~~^~~~~~~~~~~~~~
doll.cpp:69:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | if ((1 << lev) != B[i].size()) memo.back().first = r;
| ~~~~~~~~~~~^~~~~~~~~~~~~~
# | 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... |