| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 591941 | PiejanVDC | Mechanical Doll (IOI18_doll) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
void create_circuit(int m, vector<int>a) {
const int n = (int)a.size();
a.push_back(0);
vector<vector<int>>v(m+1);
vector<int>C(m+1, 0);
C[0] = a[0];
vector<int>X,Y;
for(int i = 0 ; i < n ; i++) {
v[a[i]].push_back(a[i+1]);
}
int j = 1;
for(int i = 1 ; i <= m ; i++) {
//cout << i << ' ';
if((int)v[i].size() == 0)
continue;
if(v[i].size() == 1) {
C[i] = v[i][0];
continue;
}
int p = 0;
while((1 << p) < ((v[i].size())))
p++;
vector<int>w;
if(1) {
int cnt = /*(v[i].size()&1) + 2*(((v[i].size()+1)/2)&1)*/ (1 << p) - (int)v[i].size();
for(int ii = 0 ; ii < v[i].size()/2 ; ii++)
w.push_back(v[i][ii]);
for(int ii = 0 ; ii < cnt ; ii++)
w.push_back(-j);
for(int ii = v[i].size() / 2 ; ii < v[i].size() ; ii++)
w.push_back(v[i][ii]);
v[i] = w;
}
vector<int>st(8 * (v[i].size()+1)/2, 0);
vector<int>rev(8 * (v[i].size()+1)/2);
C[i] = -j;
/*for(auto z : v[i])
cout << z << ' ';*/
//cout << i << ' ' << v[i].size() << '\n';
for(int l = 0 ; l < v[i].size()/2 ; l++) {
//cerr << l << ' ';
int pos = 1, d = 0;
while(d <= p) {
if(d < p) {
if(!st[pos]) {
st[pos] = 1;
rev[pos] = j-1;
j++;
X.push_back(INT_MAX);
Y.push_back(INT_MAX);
}
if(st[pos] == 1) {
if(!st[2*pos]) {
X[rev[pos]] = (-(j));
}
st[pos] = 2;
pos *= 2;
} else {
if(!st[2*pos+1]) {
Y[rev[pos]] = (-(j));
}
st[pos] = 1;
pos *= 2;
pos++;
}
d++;
} else {
d++;
if(!st[pos]) {
st[pos] = 1;
rev[pos] = j-1;
j++;
X.push_back(INT_MAX);
Y.push_back(INT_MAX);
}
if(st[pos] == 1) {
X[rev[pos]] = v[i][l];
st[pos] = 2;
} else {
Y[rev[pos]] = v[i][l];
st[pos] = 1;
}
}
}
}
// probeer toch EEN baan te maken en dan vooraleer te beantwoorden alles te checken dat nog geen verbinding heeft en die naar zichzelf laten gaan ofwel X en Y switchen
for(int l = v[i].size()/2 ; l < v[i].size() ; l++) {
int pos = 1, d = 0;
while(d <= p) {
if(d < p) {
d++;
if(st[pos] == 1) {
st[pos] = 2;
pos *= 2;
} else {
if(!st[2*pos+1]) {
st[pos] = 1;
Y[rev[pos]] = -rev[pos] - 1; // watch
pos *= 2;
continue;
}
st[pos] = 1;
pos *= 2;
pos++;
}
} else {
d++;
if(st[pos] == 1) {
X[rev[pos]] = -rev[pos]-1;
st[pos] = 2;
}
st[pos] = 1;
Y[rev[pos]] = v[i][l];
}
}
}
}
for(int i = 0 ; i < (int)X.size() ; i++) {
if(Y[i] == INT_MAX)
Y[i] = -i-1, swap(X[i], Y[i]);
if(Y[i] == -i-1)
swap(X[i], Y[i]);
}
/*cerr << '\n';
for(auto z : C)
cerr << z << ' ';
cerr << '\n';
for(auto z : X)
cerr << z << ' ';
cerr << '\n';
for(auto z : Y)
cerr << z << ' ';
cerr << '\n';*/
assert(X.size() < 20 000 000);
answer(C, X, Y);
}