Submission #805821

#	Time	Username	Problem	Language	Result	Execution time	Memory
805821		Ozy	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	13 ms	1724 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>

lli n,bolsa,act,mitad,w;
vector< vector<int> > res;
vector<int> trash;
vector<pll> 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;

  res.push_back(trash);
  res[0].resize(n+1);
  res[0][0] = 0;

  w = (n+1)/2;
  rep(i,1,n) {
    if (i <= w) res[0][i] = 2; //abajo
    else res[0][i] = 1; //arriba
  }
  rangos.push_back({1,n});

  bolsa = 0;
  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.second+r.first)/2;
        
        rep(i,r.first,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.first+mitad)/2;
            if (i <= w) res[pos][i] = pos+2;
            else res[pos][i] = pos+1;
          
          }
        }
        rep(i,mitad+1,r.second) { //mitad de arriba
          if (pos&1) {
            if (i == mitad+1) {res[pos][i] = escribe(bolsa);  continue;}
            if (i == r.second) {res[pos][i] = escribe(bolsa^1);  continue;}

            w = (r.second + mitad + 1)/2;
            if (i <= w) res[pos][i] = pos+3;
            else res[pos][i] = pos+2;
          }
          else res[pos][i] = escribe(bolsa^1);
        }

      }
    
    }
    
    swap(mover,rangos);
    rangos.clear();
    for(auto m : mover) {
      if (m.first == m.second) continue;
      if (m.first + 1 == m.second) continue;
      if (m.first + 2 == m.second) continue;
      mitad = (m.first + m.second)/2;
      rangos.push_back({m.first,mitad});
      rangos.push_back({mitad+1,m.second});
    }
    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: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 55 / 90