| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 599313 | MohamedFaresNebili | Mechanical Doll (IOI18_doll) | C++14 | 0 ms | 0 KiB |
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"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
const int MOD = 1e9 + 7;
void answer(vector<int> C, vector<int> X, vector<int> Y) {
int S = X.size(), M = C.size();
for(int l = 0; l < S; l++) {
cout << -(l + 1) << ": X = "
<< X[l] << " Y = " << Y[l] << "\n";
}
for(int l = 0; l < M; l++) {
cout << l << " " << C[l] << "\n";
}
}
vector<pair<int, int>> res; int D = 1;
int solve(vector<int> V, int N) {
bool ok = 1;
for(int l = 1; l < V.size(); l++)
ok &= (V[l] == V[l - 1]);
if(ok && (V.size() == 0 || V.size() == N))
return (V.size() == 0 ? -1 : V[0]);
int v = D++, i = 0, k = res.size();
vector<int> X, Y; res.push_back({-1, -1});
for(int l = 0; l < V.size() && l < N - V.size(); l++)
Y.push_back(V[i++]);
while(D < V.size()) {
X.push_back(V[D++]);
Y.push_back(V[D++]);
}
res[k] = {solve(X, N / 2), solve(Y, N / 2)};
return -v;
}
void subtask(int M, vector<int> A) {
A.push_back(0); int N = A.size(), S = 1;
while(S < N) S *= 2;
solve(A, S); vector<int> C, X, Y;
for(int l = 0; l <= M; l++)
C.push_back(-1);
for(int l = 0; l < res.size(); l++)
X.push_back(res[l].ff),
Y.push_back(res[l].ss);
answer(C, X, Y);
}
void create_circuit(int M, vector<int> A) {
if(M == 1 || A.size() == 16) {
subtask(M, A);
return;
}
int N = A.size(); A.push_back(0);
vector<int> C(M + 1, -1); N++;
set<pair<int, int>> Switches; vector<int> adj[M + 1];
pair<int, int> B[200005];
for(int l = 0; l < N; l++) {
int U = A[l], V = A[(l + 1) % N];
adj[U].push_back(V);
}
map<pair<int, int>, int> Key; int S = 0;
vector<int> X(S), Y(S);
for(int l = 0; l <= M; l++) {
if(adj[l].size() <= 1) {
adj[l].push_back(0);
C[l] = adj[l][0];
continue;
}
if(adj[l].size() == 2) {
int U = adj[l][0], V = adj[l][1];
C[l] = --S; X.push_back(U), Y.push_back(V);
continue;
}
int Q = --S; int R = --S; int E = --S;
int U = adj[l][0], V = adj[l][1];
int J = Q, K = adj[l][2];
if(adj[l].size() == 4) {
J = adj[l][3]; swap(J, K);
}
C[l] = Q; X.push_back(R); Y.push_back(E);
X.push_back(U); Y.push_back(J);
X.push_back(V); Y.push_back(K);
}
answer(C, X, Y);
}