Submission #838743

#	Time	Username	Problem	Language	Result	Execution time	Memory
838743		azatega	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	31 ms	2516 KiB

prison

#include "prison.h"

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> res;
int N;
int max_used_idx = 0;
bool used[100];

struct Range{
  int l, r;
  Range(){}
  Range(int left, int right){
    l = left;
    r = right;
  }
};

vector<vector<int>> devise_strategy(int _N) {
  N = _N;
  res.resize(100);
  for(int i = 0; i < 100; i++)
    res[i].resize(N+1);

  vector<Range> left_ranges;
  vector<Range> right_ranges;

  used[0] = true;

  right_ranges.push_back(Range(1, N));
  for(int idx = 0; idx < 100; idx++){
    if(!used[idx])
      continue;
    // turn is equal to depth % 2
    // depth is equal to idx + 1 / 2
    int depth = (idx+1)/2;
    int turn = depth % 2;
    if(idx % 2 == 1){
      // new depth, so first reset!
      vector<Range> left_ranges_new;
      vector<Range> right_ranges_new;
      for(Range rng : left_ranges){
        int l = rng.l;
        int r = rng.r;
        l++;
        r--;
        int mid = (l + r) / 2;
        left_ranges_new.push_back(Range(l, mid));
        if(mid + 1 <= r)
          right_ranges_new.push_back(Range(mid+1, r));
      }
      for(Range rng : right_ranges){
        int l = rng.l;
        int r = rng.r;
        l++;
        r--;
        int mid = (l + r) / 2;
        left_ranges_new.push_back(Range(l, mid));
        if(mid + 1 <= r)
          right_ranges_new.push_back(Range(mid+1, r));
      }

      left_ranges = left_ranges_new;
      right_ranges = right_ranges_new;

      /* cout << "Depth " << depth << " left:" << endl;
      for(Range rng : left_ranges)
        cout << rng.l << " - " << rng.r << endl; */

      res[idx][0] = turn;
      // now process
      for(int i = 1; i <= N; i++){
        bool in_range = false;
        Range rng;

        bool borders_small = false;
        bool borders_big = false;

        for(Range r : left_ranges){
            if(i >= r.l && i <= r.r){
              in_range = true;
              rng = r;
              break;
            }else if(i == r.l - 1){
              borders_small = true;
            }else if(i == r.r + 1){
              borders_big = true;
            }
        }

        if(!in_range){
          // not in the right range, so I'm in a right range... ie. bigger
          if(borders_small){
            if(turn == 0)
              res[idx][i] = -1; // im smaller
            else
              res[idx][i] = -2;
          }else if(borders_big){

            if(turn == 0)
              res[idx][i] = -2; // im bigger
            else
              res[idx][i] = -1;
          }else if(turn == 0)
            res[idx][i] = -2; // im bigger
          else
            res[idx][i] = -1;
        }else if(i == rng.l){
          // im definitely smaller
          if(turn == 0)
            res[idx][i] = -1; // im smaller
          else
            res[idx][i] = -2;       
        }else if(i == rng.r){
          // im definitely bigger
          if(turn == 0)
            res[idx][i] = -2; // im bigger
          else
            res[idx][i] = -1;   
        }else{
          int mid = (rng.l + rng.r) / 2;
          if(i <= mid){
            // left je sljedeci + 1 jer sam u lijevom
            res[idx][i] = idx+2;
            used[idx+2] = true;
          }else{
            // right je sljedeci + 2 jer sam u lijevom
            res[idx][i] = idx+3;
            used[idx+3] = true;
          }
        }
      }
    }else{
      /* cout << "Depth " << depth << " right:" << endl;
      for(Range rng : right_ranges)
        cout << rng.l << " - " << rng.r << endl; */
      
      res[idx][0] = turn;
      // same depth, but right
      for(int i = 1; i <= N; i++){
        bool in_range = false;
        Range rng;

        bool borders_small = false;
        bool borders_big = false;

        for(Range r : right_ranges){
            if(i >= r.l && i <= r.r){
              in_range = true;
              rng = r;
              break;
            }else if(i == r.l - 1){
              borders_small = true;
            }else if(i == r.r + 1){
              borders_big = true;
            }
        }

        if(!in_range){
          // not in the right range, so I'm in a left range... ie. smaller
          if(borders_small){
            if(turn == 0)
              res[idx][i] = -1; // im smaller
            else
              res[idx][i] = -2;
          }else if(borders_big){

            if(turn == 0)
              res[idx][i] = -2; // im bigger
            else
              res[idx][i] = -1;
          }else if(turn == 0)
            res[idx][i] = -1; // im smaller
          else
            res[idx][i] = -2;
        }else if(i == rng.l){
          // im definitely smaller
          if(turn == 0)
            res[idx][i] = -1; // im smaller
          else
            res[idx][i] = -2;       
        }else if(i == rng.r){
          // im definitely bigger
          if(turn == 0)
            res[idx][i] = -2; // im bigger
          else
            res[idx][i] = -1;   
        }else{
          int mid = (rng.l + rng.r) / 2;
          if(i <= mid){
            // left je sljedeci jer sam u desnom
            res[idx][i] = idx+1;
            used[idx+1] = true;
          }else{
            // right je sljedeci + 1 jer sam u desnom
            res[idx][i] = idx+2;
            used[idx+2] = true;
          }
        }
      }
    } 
  }

  int max_used = 0;
  for(int i = 0; i < 100; i++)
    if(used[i])
      max_used = max(max_used, i);
  res.resize(max_used + 1);

  //for(int i = 0; i < max_used; i++)
  //  cout << res[i][2] << " " << res[i][4] << " turn is " << res[i][0] << endl;

  return res;
}

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