| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1231274 | acoatoitgs | Mechanical Doll (IOI18_doll) | C++20 | 0 ms | 0 KiB |
#include "doll.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll int
#define all(a) (a).begin(), (a).end()
void create_circuit(int M, vector<int> A) {
int N = A.size();
A.push_back(0);
vector<int> C(M + 1);
vector<vector<pair<int,int>>> con(M+1);
bitset<100005> uniq;
uniq.flip();
bitset<100005> seen;
for(ll i = 0; i < N; i++)
{
if(seen[A[i]]) uniq[A[i]] = 0;
seen[A[i]] = 1;
}
int len = 0;
int nx = -1;
for(int i = 0; i < N; i++)
{
len += (!uniq[A[i]]);
}
for(int i = 1; i <= M; i++)
{
if(!seen[i]) C[i] = 0;
}
// cout << "LEN: " << len << "\n";
vector<int> X(N + 50), Y(N + 50);
C[0] = A[0];
int depth = max(1, (__builtin_popcount(len) == 1) ?
__bit_width((uint32_t)len)-1 :
__bit_width((uint32_t)len));
int first_node = -1;
// cout << depth << " " << first_node << "\n";
vector<pair<ll,pair<ll, bool>>> tm;
function<int(int, int)> prop = [&](int val, int dep) -> int
{
// cout << val << " " << dep << "\n";
int node = nx;
nx--;
if(dep == depth-1)
{
int val1 = val;
int val2 = val + (1<<dep);
if(tm.size() < len)
{
tm.push_back({val1, {node, 0}});
tm.push_back({val2, {node, 1}});
return node;
}
else
{
nx++;
return first_node;
}
}
else
{
int y = prop(val+(1<<dep), dep+1);
int x = prop(val, dep+1);
X[-(node+1)] = x;
Y[-(node+1)] = y;
return node;
}
};
if(len != 0)
prop(0, 0);
// cout << "SZ: " << tm.size() << "\n";
sort(all(tm), greater<pair<ll, pair<ll, bool>>>());
int idx = 0;
while(len > 1 && idx < N)
{
if(uniq[A[idx]])
{
C[A[idx]] = A[idx+1];
idx++;
continue;
}
else C[A[idx]] = first_node;
int to = A[idx+1];
auto [node, r] = tm.back().second;
tm.pop_back();
if(r) Y[-(node+1)] = to;
else X[-(node+1)] = to;
idx++;
len--;
}
// cout << len << " " << idx << "\n";
while(tm.size() != 1)
{
auto [node, r] = tm.back().second;
tm.pop_back();
if(r) Y[-(node+1)] = -1;
else X[-(node+1)] = -1;
}
while(idx < N)
{
// cout << "In: " << idx << " " << uniq[A[idx]] << " " << tm.size() << "\n";
if(uniq[A[idx]])
{
C[A[idx]] = A[idx+1];
idx++;
continue;
}
else C[A[idx]] = first_node;
int to = A[idx+1];
auto [node, r] = tm.back().second;
tm.pop_back();
if(r) Y[-(node+1)] = to;
else X[-(node+1)] = to;
idx++;
len--;
}
X.resize(-(nx+1));
Y.resize(-(nx+1));
answer(C, X, Y);
}