Submission #1014560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014560		kunzaZa183	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	8 ms	1372 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>
using namespace std;

struct seg {
  pair<int, int> old, cur;
};

vector<vector<int>> devise_strategy(int N) {

  vector<vector<int>> vvi;
  vector<vector<seg>> help;
  help.push_back(vector<seg>());

  vector<seg> vs;
  seg tmp;
  tmp.old = {1, N};
  vvi.push_back(vector<int>(N + 1));
  vvi[0][0] = 0;
  for (int i = tmp.old.first; i >= 1; i--) vvi[0][i] = -1;
  for (int i = tmp.old.second; i <= N; i++) vvi[0][i] = -2;
  tmp.cur = {2, (N + 1) / 2};
  for (int i = tmp.cur.first; i <= tmp.cur.second; i++) vvi[0][i] = 1;
  vs.push_back(tmp);
  help.push_back(vs);

  vs.clear();
  tmp.cur = {(N + 1) / 2 + 1, N - 1};
  for (int i = tmp.cur.first; i <= tmp.cur.second; i++) vvi[0][i] = 2;
  vs.push_back(tmp);
  help.push_back(vs);

  for (int i = 1; 1; i += 2) {
    int curi = i;
    for (int j=0;j<2;j++)
      help.push_back(vector<seg>());
    do {
      vvi.push_back(vector<int>(N + 1));
      if (curi % 4 == 1) vvi[i][0] = 1;
      for (auto a : help[i]) {
        for (int j = a.cur.first; j >= a.old.first; j--) {
          if (curi % 4 == 1)
            vvi[i][j] = -2;
          else
            vvi[i][j] = -1;
        }

        for (int j = a.cur.second; j <= a.old.second; j++) {
          if (curi % 4 == 1)
            vvi[i][j] = -1;
          else
            vvi[i][j] = -2;
        }
        seg tmp, tmp2;
        tmp.old = a.cur;
        tmp2.old = a.cur;

        if ((tmp.old.second - tmp.old.first) % 2 == 1) {
          tmp.cur = {tmp.old.first + 1, (tmp.old.first + tmp.old.second) / 2};
          tmp2.cur = {(tmp.old.first + tmp.old.second) / 2 + 1,
                      tmp.old.second - 1};
        } else {
          tmp.cur = {tmp.old.first + 1, (tmp.old.first + tmp.old.second) / 2};
          tmp2.cur = {(tmp.old.first + tmp.old.second) / 2 + 1,
                      tmp.old.second - 1};
          if (curi % 4==1)
          {
            tmp.cur.second--;
            tmp2.cur.first--;
          }
        }
        help[curi + 2].push_back(tmp);
        help[curi + 3].push_back(tmp2);
        for (int j = tmp.cur.first;
             j <= tmp.cur.second; j++)
          vvi[i][j] = curi + 2;

        for (int j = tmp2.cur.first;
             j <= tmp2.cur.second; j++)
          vvi[i][j] = curi + 3;
      }
      i++;
    } while (i % 2 == 0);

    i -= 2;

    for (int j = 1; j <= N; j++)
      if (vvi[i][j] > 0 || vvi[i + 1][j] > 0) goto A;
    if(vvi.size()==23)
      vvi.pop_back();
    return vvi;
  A:;
  }
}

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