제출 #805899

#제출 시각아이디문제언어결과실행 시간메모리
805899Ozy죄수들의 도전 (IOI22_prison)C++17
0 / 100
1 ms296 KiB
#include "prison.h" #include <bits/stdc++.h> using namespace std; #define lli long long int #define debug(a) cout << #a << " = " << a << endl #define debugsl(a) cout << #a << " = " << a << ", " #define rep(i,a,b) for(int i = (a); i <= (b); i++) #define repa(i,a,b) for(int i = (a); i >= (b); i--) #define pll pair<lli,lli> struct x { lli ini; lli fin; lli izq; lli der; }; lli n,bolsa,act,mitad,w; vector< vector<int> > res; vector<int> trash; vector<x> rangos,mover; lli escribe(lli b) { b *= (-1); b -= 1; return b; } std::vector<std::vector<int>> devise_strategy(int N) { // dividir (1,2) para pregutar por B y (3,4) para volver a preguntar por A n = N; bolsa = 0; res.push_back(trash); res[0].resize(n+1); res[0][0] = bolsa; w = (n+1)/2; rep(i,1,n) { if (i <= w) res[0][i] = 2; //abajo else res[0][i] = 1; //arriba } res[0][1] = escribe(bolsa); res[0][n] = escribe(bolsa^1); if (n > 2) rangos.push_back({2,n-1,1,1}); act = 1; while (!rangos.empty()) { bolsa ^= 1; res.push_back(trash); res[act].resize(n+1); res.push_back(trash); res[act+1].resize(n+1); rep(pos,act,act+1) { res[pos][0] = bolsa; for(auto r : rangos) { mitad = (r.fin + r.ini)/2; rep(i,r.ini,mitad) {// mitad de abajo if (pos&1) res[pos][i] = escribe(bolsa); else { //if (i == r.first) {res[pos][i] = escribe(bolsa); continue;} //if (i == mitad) {res[pos][i] = escribe(bolsa^1); continue;} w = (r.ini+mitad)/2; if (i <= w) res[pos][i] = pos+2; else res[pos][i] = pos+1; } } rep(i,mitad+1,r.fin) { //mitad de arriba if (pos&1) { //if (i == mitad+1) {res[pos][i] = escribe(bolsa); continue;} //if (i == r.fin) {res[pos][i] = escribe(bolsa^1); continue;} w = (r.fin + mitad + 1)/2; if (i <= w) res[pos][i] = pos+3; else res[pos][i] = pos+2; } else res[pos][i] = escribe(bolsa^1); } repa(i,r.ini,r.ini+r.izq) res[pos][i] = escribe(bolsa); rep(i,r.fin,r.fin+r.der) res[pos][i] = escribe(bolsa^1); } } swap(mover,rangos); rangos.clear(); for(auto m : mover) { if (m.ini == m.fin) continue; if (m.ini + 1 == m.fin) continue; if (m.ini + 2 == m.fin) continue; mitad = (m.ini + m.fin)/2; rangos.push_back({m.ini,mitad,m.izq+1,1}); rangos.push_back({mitad+1,m.fin,1,m.der+1}); } act += 2; } act = res.size()-1; rep(i,0,act) { rep(j,1,n) { if (res[i][j] > act) res[i][j] = -1; } } return res; } // tener cuidado ya que la implementacion puede dejar valores mayores a x, eso es un wa (sube las x)
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...