Submission #838692

#	Time	Username	Problem	Language	Result	Execution time	Memory
838692		azatega	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	2 ms	2132 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];

void set_strategy(int turn, int idx, vector<pair<int, int>> ranges, bool is_left){
  res[idx][0] = turn;
  used[idx] = true;
  max_used_idx = max(idx, max_used_idx);

  bool needs_left = false;
  bool needs_right = false;
  vector<pair<int, int>> left_ranges;
  vector<pair<int, int>> right_ranges;
  for(pair<int, int> range : ranges){
    int l = range.first;
    int r = range.second;

    //l++;
    //r--;

    if(r - l >= 1){
      int mid = (l+r) / 2;
      left_ranges.push_back({l, mid});
      needs_left = true;

      if(mid+1 <= r){
        right_ranges.push_back({mid+1, r});
        needs_right = true;
      }
    }
  }

  //cout << "still alive" << endl;
  int left_idx = -5;
  int right_idx = -5;
  if(needs_left){
    for(int i = 0; i < 100; i++){
      if(used[i] == false){
        left_idx = i;
        used[i] = true;
        break;
      }
    }
  }
  if(needs_right){
    for(int i = 0; i < 100; i++){
      if(used[i] == false){
        right_idx = i;
        used[i] = true;
        break;
      }
    }
  }

  for(int i = 1; i <= N; i++){
    bool in_range = false;
    pair<int, int> range;

    for(pair<int, int> range_t : ranges){
      if(i >= range_t.first && i <= range_t.second){
        in_range = true;
        range = range_t;
      }
    }

    if(!in_range){
      // znamo sta smo
      if(is_left){
        // ovo je indeks za lijevi range, znaci ja sam desni -> veci!
        // dakle rjesenje je druga vreca jer je ona manja
        if(turn == 0)
          res[idx][i] = -2;
        else
          res[idx][i] = -1;
      }else{
        // ovo je indeks za desni range, znaci ja sam lijevo -> manji!
        // dakle rjesenje je ova vreca (ja)
        if(turn == 0)
          res[idx][i] = -1;
        else
          res[idx][i] = -2;
      }
    }else{
      // provjerimo jesmo li na cosku range-a
      // ili na nekoj strani
      if(i == range.first){
        // mi smo sigurno manji
        if(turn == 0)
          res[idx][i] = -1;
        else
          res[idx][i] = -2;
      }else if(i == range.second){
        // mi smo sigurno veci
        if(turn == 0)
          res[idx][i] = -2;
        else
          res[idx][i] = -1;
      }else{
        //range.first++;
        //range.second--;

        int mid = (range.first + range.second)/2;
        // idemo ili lijevo (idx+1) ili desno (idx+2)
        if(i <= mid)
          res[idx][i] = left_idx;
        else
          res[idx][i] = right_idx;
      }
    }
  }

  //cout << left_idx << " " << right_idx << endl;

  if(needs_left){
    if(turn == 0)
      set_strategy(1, left_idx, left_ranges, true);
    else
      set_strategy(0, left_idx, left_ranges, true);
  }

  if(needs_right){
    if(turn == 0)
      set_strategy(1, right_idx, right_ranges, false);
    else
      set_strategy(0, right_idx, right_ranges, false);
  }
}

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<pair<int, int>> ranges;
  ranges.push_back({1, N});

  set_strategy(0, 0, ranges, true);
  res.resize(max_used_idx+1);
  return res;
}

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