제출 #627021

#제출 시각아이디문제언어결과실행 시간메모리
627021LeMur죄수들의 도전 (IOI22_prison)C++17
0 / 100
10 ms1868 KiB
#include "prison.h" #include <vector> #include <iostream> using namespace std; const int N = 20005; int l[N], r[N]; int depth[N], id[N]; vector <int> children[N]; vector < pair<int, int> > vertices[30]; vector < vector<int> > answ; int it = 1; int max_height = 0; void rec(int v, int s, int e, int h) { max_height = max(max_height, h); /// depth[v] = h; l[v] = s; r[v] = e; /// int len = e - s + 1; if (len <= 2) return ; int rem = len % 3; int cur_start = s; for (int i = 1; i <= 3; i++) { int cur_len = len / 3; if (rem > 0) { cur_len++; --rem; } ++it; id[it] = 3 * ((id[v] + 2) / 3) + i; /// vertices[ id[it] ].push_back( make_pair(v, it) ); /// children[v].push_back(it); rec(it, cur_start, cur_start + cur_len - 1, h + 1); cur_start += cur_len; } } vector < vector<int> > devise_strategy(int n) { id[1] = 0; rec(1, 1, n, 0); answ.resize(3 * max_height + 1); answ[0].resize(n + 1, 0); answ[0][0] = 0; if (n == 2) { answ[0][1] = -1; answ[0][2] = -2; } else { for (int i = 1; i <= n; i++) { for (int j = 0; j < (int)children[1].size(); j++) { int vertex = children[1][j]; if (i >= l[vertex] && i <= r[vertex]) { answ[0][i] = id[vertex]; } } } } for (int x = 1; x <= 3 * max_height; x++) { answ[x].resize(n + 1, 0); /// answ[x][0] = ((x + 2) / 3) % 2; /// for (int ii = 0; ii < (int)vertices[x].size(); ii++) { int parent = vertices[x][ii].first; int current = vertices[x][ii].second; for (int i = l[parent]; i <= r[parent]; i++) { if (i < l[current]) { if (answ[x][0] == 0) { answ[x][i] = -1; } else { answ[x][i] = -2; } } else if (i > r[current]) { if (answ[x][0] == 0) { answ[x][i] = -2; } else { answ[x][i] = -1; } } else { if ((int)children[current].size() == 3) { for (int j = 0; j < (int)children[current].size(); j++) { int vertex = children[current][j]; if (i >= l[vertex] && i <= r[vertex]) { answ[x][i] = id[vertex]; } } } else { if (i == l[parent]) { if (answ[x][0] == 0) { answ[x][i] = -1; } else { answ[x][i] = -2; } } else { if (answ[x][0] == 0) { answ[x][i] = -2; } else { answ[x][i] = -1; } } } } } } } // for (int x = 0; x <= 3 * max_height; x++) { // for (int j = 0; j <= n; j++) { // cout << answ[x][j] << " "; // } // cout << endl; // } return answ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...