| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 418547 | EncryptingWolf | Mechanical Doll (IOI18_doll) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <vector>
#include "dolls.h"
#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
typedef long long ll;
#define FOR(i,x,y) for (ll i = x; i<y; i++)
using namespace std;
long long reverse(long long a, long long num)
{
long long p = long long(log2(num) + 0.001);
ll r=0;
FOR(i, 0, p)
{
if ((a >> i) & 1)
{
r +=( 1 << (p - i-1));
}
}
return r;
}
void create_circuit(int M, vector<int> A)
{
A.push_back(0);
M += 1;
vector<int> connections(M,0);
connections[0] = A[0];
vector<pair<int,int>> switches;
vector<vector<int>> follow(M);
FOR(i, 0, A.size() - 1)
{
follow[A[i]].push_back(A[i + 1]);
}
int lowestSwitch = -1;
FOR(i,1,M)
{
if (follow[i].size() == 1)
{
connections[i]=follow[i][0];
}
else if (follow[i].size() ==0)
{
continue;
}
else
{
connections[i] = lowestSwitch;
switches.push_back({});
lowestSwitch--;
int switchStart = lowestSwitch;
int num = 1;
while (num*2 < follow[i].size())
{
int firstSwitch = switches.size() - num;
FOR(j, firstSwitch, firstSwitch+num)
{
switches[j].first = lowestSwitch;
switches[j].second = lowestSwitch-1;
lowestSwitch -= 2;
switches.push_back({});
switches.push_back({});
}
num *= 2;
}
int firstSwitch = switches.size() - num;
int outnum = num * 2;
int z = 0;
FOR(k, 0, outnum)
{
int j = reverse(k, outnum)+ (firstSwitch * 2);
if (outnum > follow[i].size())
{
if (j % 2 == 0)
{
switches[j / 2].first = switchStart;
}
if (j % 2 == 1)
{
switches[j / 2].second = switchStart;
}
}
else
{
if (j % 2 == 0)
{
switches[j / 2].first = follow[i][z];
}
if (j % 2 == 1)
{
switches[j / 2].second = follow[i][z];
}
z++;
}
}
}
}
vector<int> X, Y;
FOR(i, 0, switches.size())
{
X.push_back(switches[i].first);
Y.push_back(switches[i].second);
}
answer(connections, X, Y);
}