# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
371616 | Lam_lai_cuoc_doi | Painting Squares (IOI20_squares) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const int N = 1e3 + 5;
map<int, int> ck;
int a[N], m, s, ans;
bool dfs(int v, int dep)
{
ck[v] = dep;
if (dep == 971)
return true;
int u = v >> 1;
if (!ck[u + (1 << 29)])
if (dfs(u + (1 << 29), dep + 1))
return true;
if (!ck[u])
if (dfs(u, dep + 1))
return true;
return false;
}
void fillout(int v, int dep)
{
if (dep > m - 30 + 1)
return;
if (s == v)
{
ans = dep - 1;
return;
}
int u = v >> 1;
if (ck[u] == dep + 1)
fillout(u, dep + 1);
else if (ck[u + (1 << 29)] == dep + 1)
fillout(u + (1 << 29), dep + 1);
}
void fillin(int v, int dep)
{
if (dep == m - 30 + 1)
{
for (int i = 0; i < 30; ++i)
a[m - 30 + 1 + i] = (v >> i) & 1;
return;
}
a[dep - 1] = v & 1;
int u = v >> 1;
if (ck[u] == dep + 1)
fillin(u, dep + 1);
else if (ck[u + (1 << 29)] == dep + 1)
fillin(u + (1 << 29), dep + 1);
}
int *paint(int n)
{
if (n <= 30)
{
for (int i = 0; i < n; ++i)
a[i] = 1;
a[n] = n;
return a;
}
m = n;
ck.clear();
ck[1] = 1;
dfs(1, 1);
fillin(1, 1);
return a;
}
int find_location(int n, int c[])
{
if (n <= 30)
{
for (int i = 0; i < n; ++i)
if (c[i] != 1)
return -1;
return 0;
}
m = n;
ck.clear();
ck[1] = 1;
dfs(1, 1);
s = 0;
for (int i = 0; i < 30; ++i)
s += (a[i]) * (1 << i);
ans = -1;
fillout(1, 1);
return ans;
}