Submission #805899

#	Time	Username	Problem	Language	Result	Execution time	Memory
805899		Ozy	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	1 ms	296 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;
};

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)

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