oj.uz

Submission #1014560

# Submission time Handle Problem Language Result Execution time Memory
1014560 2024-07-05T07:00:23 Z kunzaZa183 Prisoner Challenge (IOI22_prison) C++17
90 / 100
 8 ms 1372 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 432 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 408 KB Output is correct

Subtask #3
80.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 5 ms 728 KB Output is correct
5 Partially correct 6 ms 1096 KB Output is partially correct
6 Partially correct 7 ms 1372 KB Output is partially correct
7 Partially correct 8 ms 1372 KB Output is partially correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 6 ms 856 KB Output is correct