| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 316373 | alextodoran | Mechanical Doll (IOI18_doll) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
typedef long long ll;
struct XYSwitch
{
int X, Y;
bool state;
};
vector <XYSwitch> switches;
int createInfiniteSwitch (int N, int firstPos, int level)
if(level == 0)
{
if(N == 0)
{
int X = -777777777;
int Y = -777777777;
switches.push_back(XYSwitch{X, Y});
return (int)switches.size() - 1;
}
if(N == 1)
{
int X = -firstPos;
int Y = -777777777;
switches.push_back(XYSwitch{X, Y});
return (int)switches.size() - 1;
}
if(N == 2)
{
int X = -firstPos;
int Y = -(firstPos + 1);
switches.push_back(XYSwitch{X, Y});
return (int)switches.size() - 1;
}
}
int L;
if(N > 0)
{
int p2 = 0;
while((1 << (p2 + 1)) < N)
p2++;
L = (1 << p2);
}
else
L = 0;
int X = createInfiniteSwitch(L, firstPos, level - 1);
int Y = createInfiniteSwitch(N - L, firstPos + L, level - 1);
switches.push_back(XYSwitch{X, Y, false});
return (int)switches.size() - 1;
}
int createFiniteSwitch (int N, int firstPos, int level)
{
if(level == 0)
{
if(N == 0)
{
int X = -777777777;
int Y = 0;
switches.push_back(XYSwitch{X, Y, false});
return (int)switches.size() - 1;
}
if(N == 1)
{
int X = -firstPos;
int Y = 0;
switches.push_back(XYSwitch{X, Y, false});
return (int)switches.size() - 1;
}
}
int L;
if(N > 0)
{
int p2 = 0;
while((1 << (p2 + 1)) < N)
p2++;
L = (1 << p2);
}
else
L = 0;
int X = createInfiniteSwitch(L, firstPos, level - 1);
int Y = createFiniteSwitch(N - L, firstPos + L, level - 1);
switches.push_back(XYSwitch{X, Y, false});
return (int)switches.size() - 1;
}
vector <int> triggers;
int curr;
bool dfs (int u)
{
if(u < 0)
{
triggers[-u] = curr;
return true;
}
if(u == 0)
return false;
switches[u].state ^= 1;
if(switches[u].state == true)
return dfs(switches[u].X);
else
return dfs(switches[u].Y);
}
void create_circuit(int M, vector <int> A)
{
int N = A.size();
switches.clear();
switches.push_back(XYSwitch{0, 0, false});
int p2 = 0;
while((1 << (p2 + 1)) <= N)
p2++;
int root = createFiniteSwitch(N, 1, p2 - 1);
for(int i = 1; i < (int)switches.size(); i++)
{
if(switches[i].X == -777777777)
switches[i].X = root;
if(switches[i].Y == -777777777)
switches[i].Y = root;
}
triggers.clear();
triggers.resize(M + 1);
for(int i = 0; i < N; i++)
{
curr = A[i];
while(true)
{
if(dfs(root) == true)
break;
}
}
vector <int> X(switches.size() - 1), Y(switches.size() - 1), C(M + 1);
for(int i = 1; i < (int)switches.size(); i++)
{
if(switches[i].X < 0)
X[i - 1] = triggers[-switches[i].X];
else
X[i - 1] = -switches[i].X;
if(switches[i].Y < 0)
Y[i - 1] = triggers[-switches[i].Y];
else
Y[i - 1] = -switches[i].Y;
}
C[0] = -root;
for(int i = 1; i <= M; i++)
C[i] = root;
answer(C, X, Y);
}