Submission #1014533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014533		kunzaZa183	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	1 ms	348 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) {
    do {
      vvi.push_back(vector<int>(N + 1));
      if(i%4==1)
        vvi[i][0] = 1;
      vector<seg> vsg;
      for (auto a : help[i]) {
        for (int j = a.cur.first; j >= a.old.first; j--) {
          if (i % 4 == 1)
            vvi[i][j] = -2;
          else
            vvi[i][j] = -1;
        }

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

        seg tmp;
        tmp.old = a.cur;
        tmp.cur = {tmp.old.first + 1, (tmp.old.first + tmp.old.second) / 2};
        vsg.push_back(tmp);
        tmp.cur = {(tmp.old.first + tmp.old.second) / 2 + 1,
                   tmp.old.second - 1};
        vsg.push_back(tmp);

        for (int j = tmp.old.first + 1;
             j <= (tmp.old.first + tmp.old.second) / 2; j++)
          vvi[i][j] = i + 2;

        for (int j = (tmp.old.first + tmp.old.second) / 2 + 1;
             j <= tmp.old.second - 1; j++)
          vvi[i][j] = i + 3;
      }
      help.push_back(vsg);
      i++;
    } while (i % 2 == 0);

    i -= 2;

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

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