Submission #805954

#	Time	Username	Problem	Language	Result	Execution time	Memory
805954		Ozy	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	9 ms	1492 KiB

prison

#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;
};

int MAX;
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;
  MAX = 0;
  
  bolsa = 0;
  res.push_back(vector<int> (n + 1));
  res[0][0] = bolsa;
  
  w = (n+1)/2;
  rep(i,1,n) {
    if (i <= w) res[0][i] = 1; //abajo
    else res[0][i] = 2; //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()) {
    
    //debug(act);
    
    bolsa ^= 1;
    res.push_back(vector<int> (n + 1));
    res.push_back(vector<int> (n + 1));
  
    rep(pos,act,act+1) {
    
      res[pos][0] = bolsa;
      for(auto r : rangos) {
        //debugsl(r.ini);
        //debugsl(r.fin);
        //debugsl(r.izq);
        //debug(r.der);

        mitad = (r.fin + r.ini)/2;
        
        rep(i,r.ini,mitad) {// mitad de abajo
          if (!(pos&1)) res[pos][i] = escribe(bolsa);
          else {
            w = (r.ini+mitad)/2;
            if (i <= w) res[pos][i] = pos+2;
            else res[pos][i] = pos+3; 
          }
        }
        rep(i,mitad+1,r.fin) { //mitad de arriba
          if (!(pos&1)) {
            w = (r.fin + mitad + 1)/2;
            if (i <= w) res[pos][i] = pos+1;
            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;
      mitad = (m.ini + m.fin)/2;
      res[act+1][mitad+1] = escribe(bolsa);
      res[act][mitad] = escribe(bolsa^1);
      if (m.ini+1 <=  mitad-1) rangos.push_back({m.ini+1,mitad-1,m.izq+1,1});
      if (m.fin-1 >=  mitad+2) rangos.push_back({mitad+2,m.fin-1,1,m.der+1});
    }

    //rep(i,0,n) cout << res[act][i] << ' ';
    //cout << endl;
    //rep(i,0,n) cout << res[act+1][i] << ' ';
    //cout << endl;

    act += 2;
  }
  
  act = res.size()-1;
  rep(i,0,act) {
    rep(j,1,n) {
      if (res[i][j] > act) res[i][j] = -1;
      MAX = max(MAX,res[i][j]);
    }
  }

  if (MAX < act) res.pop_back();
  
  //debug(res.size() - 1);
  return res;
}
  
// tener cuidado ya que la implementacion puede dejar valores mayores a x, eso es un wa (sube las x)

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 80 / 90