# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1077073 | Trent | 로봇 대회 (IOI23_robot) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "beechtree.h"
#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
#define asst(x) if(!(x)) exit(2)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
vi sub(int T, vi& P) {
set<int> in;
in.insert(T);
int N = P.size();
while(true) {
bool hasNew = false;
forR(i, N) {
if(in.count(P[i]) && !in.count(i)) {
hasNew = true;
in.insert(i);
}
}
if(!hasNew) break;
}
vi ret;
for(int i : in) ret.push_back(i);
return ret;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
vi ret(N);
if(N <= 8) {
forR(i, N) {
vi vals = sub(i, P);
sort(all(vals));
bool found = false;
do {
bool can = vals[0] == i;
map<int, int> freq;
for(int j : vals) {
can = can && P[j] == vals[freq[C[j]]];
++freq[C[j]];
}
found = found || can;
} while(next_permutation(all(vals)));
ret[i] = found;
}
}
bool can = true;
int lasCol = -1;
for(int i = N-1; i >= 0; --i) {
if(can) {
ret[i] = 1;
if(lasCol == -1) lasCol = C[i];
else can = can && C[i] == lasCol;
} else {
ret[i] = 0;
}
}
return ret;
}