제출 #1032436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032436		Mr_Husanboy	죄수들의 도전 (IOI22_prison)	C++17	90 / 100	7 ms	1116 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long

template<typename T>
int len(T &a){
    return a.size();
}

#define a -1
#define b -2

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());



vector<std::vector<int>> devise_strategy(int n) {
  vector<vector<int>> res;

  auto construct = [&](auto &construct, int step, int i, int box, int al, int ar, int bl, int br)->void{
    //cout << i << ' ' << box << ' ' << al << ' ' << ar << ' ' << bl << ' ' << br << endl;
    if(box == 0){
      if(bl > br) return;
      while(len(res) <= i) res.push_back(vector<int>(n + 1));
      //cout << len(res) << endl;
      res[i][0] = 0;
      //cout << al << ' ' << ar << endl;
      for(int j = al; j <= bl; j ++){
        res[i][j] = a;
      }
      for(int j = br; j <= ar; j ++){
        res[i][j] = b;
      }

      al = bl + 1;
      ar = br - 1;
      if(al > ar) return;
      int mid = (al + ar) / 2;
      for(int j = al; j <= mid; j ++) res[i][j] = step * 2 - 1;
      for(int j = mid + 1; j <= ar; j ++) res[i][j] = step * 2;
      construct(construct, step + 1, step * 2 - 1, box ^ 1, al, mid, bl, br);
      construct(construct, step + 1, step * 2, box ^ 1, mid + 1, ar, bl, br);
    }else{
      if(al > ar) return;
      while(len(res) <= i) res.push_back(vector<int>(n + 1));
      res[i][0] = 1;
      for(int j = bl; j <= al; j ++){
        res[i][j] = b;
      }
      for(int j = ar; j <= br; j ++){
        res[i][j] = a;
      }
      bl = al + 1;
      br = ar - 1;
      if(bl > br) return;
      int mid = (bl + br) / 2;
      for(int j = bl; j <= mid; j ++){
        res[i][j] = step * 2 - 1;
      }
      for(int j = mid + 1; j <= br; j ++){
        res[i][j] = step * 2;
      }
      construct(construct, step + 1, step * 2 - 1, box ^ 1, al, ar, bl, mid);
      construct(construct, step + 1, step * 2, box ^ 1, al, ar, mid + 1, br);
    }
  };  
  construct(construct, 1, 0, 0, 1, n, 1, n);
  return res;
}

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