제출 #1014543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1014543		kunzaZa183	죄수들의 도전 (IOI22_prison)	C++17	80 / 100	7 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;
        tmp.old = a.cur;
        tmp.cur = {tmp.old.first + 1, (tmp.old.first + tmp.old.second) / 2};
        help[curi + 2].push_back(tmp);
        tmp.cur = {(tmp.old.first + tmp.old.second) / 2 + 1,
                   tmp.old.second - 1};
        help[curi + 3].push_back(tmp);

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

        for (int j = (tmp.old.first + tmp.old.second) / 2 + 1;
             j <= tmp.old.second - 1; 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;
    return vvi;
  A:;
  }
}

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