oj.uz

Submission #1032436

# Submission time Handle Problem Language Result Execution time Memory
1032436 2024-07-23T18:36:49 Z Mr_Husanboy Prisoner Challenge (IOI22_prison) C++17
90 / 100
 7 ms 1116 KB 
#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long

template<typename T>
int len(T &a){
    return a.size();
}

#define a -1
#define b -2

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());



vector<std::vector<int>> devise_strategy(int n) {
  vector<vector<int>> res;

  auto construct = [&](auto &construct, int step, int i, int box, int al, int ar, int bl, int br)->void{
    //cout << i << ' ' << box << ' ' << al << ' ' << ar << ' ' << bl << ' ' << br << endl;
    if(box == 0){
      if(bl > br) return;
      while(len(res) <= i) res.push_back(vector<int>(n + 1));
      //cout << len(res) << endl;
      res[i][0] = 0;
      //cout << al << ' ' << ar << endl;
      for(int j = al; j <= bl; j ++){
        res[i][j] = a;
      }
      for(int j = br; j <= ar; j ++){
        res[i][j] = b;
      }

      al = bl + 1;
      ar = br - 1;
      if(al > ar) return;
      int mid = (al + ar) / 2;
      for(int j = al; j <= mid; j ++) res[i][j] = step * 2 - 1;
      for(int j = mid + 1; j <= ar; j ++) res[i][j] = step * 2;
      construct(construct, step + 1, step * 2 - 1, box ^ 1, al, mid, bl, br);
      construct(construct, step + 1, step * 2, box ^ 1, mid + 1, ar, bl, br);
    }else{
      if(al > ar) return;
      while(len(res) <= i) res.push_back(vector<int>(n + 1));
      res[i][0] = 1;
      for(int j = bl; j <= al; j ++){
        res[i][j] = b;
      }
      for(int j = ar; j <= br; j ++){
        res[i][j] = a;
      }
      bl = al + 1;
      br = ar - 1;
      if(bl > br) return;
      int mid = (bl + br) / 2;
      for(int j = bl; j <= mid; j ++){
        res[i][j] = step * 2 - 1;
      }
      for(int j = mid + 1; j <= br; j ++){
        res[i][j] = step * 2;
      }
      construct(construct, step + 1, step * 2 - 1, box ^ 1, al, ar, bl, mid);
      construct(construct, step + 1, step * 2, box ^ 1, al, ar, mid + 1, br);
    }
  };  
  construct(construct, 1, 0, 0, 1, n, 1, n);
  return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 352 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 476 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 444 KB Output is correct
9 Correct 1 ms 444 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 504 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 0 ms 356 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 1 ms 352 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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Partially correct 6 ms 832 KB Output is partially correct
6 Partially correct 7 ms 1112 KB Output is partially correct
7 Partially correct 7 ms 1116 KB Output is partially correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 2 ms 608 KB Output is correct
11 Correct 3 ms 608 KB Output is correct
12 Correct 5 ms 860 KB Output is correct