oj.uz

Submission #719554

# Submission time Handle Problem Language Result Execution time Memory
719554 2023-04-06T09:39:12 Z veehz Prisoner Challenge (IOI22_prison) C++17
80 / 100
 14 ms 1020 KB 
#include "prison.h"

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

int get_num(int digit, int pos) {
  if (pos < 7)
    return 3 * pos + digit + 1;
  else
    return get_num(2, 6) + 1;
}

string base3(int n) {
  string s;
  while (n) {
    s += (n % 3) + '0';
    n /= 3;
  }
  while (s.size() < 8) s += '0';
  reverse(s.begin(), s.end());
  return s;
}

int whichBag(int pos, int ifA, int ifB) {
  if (pos % 2) return ifA;
  return ifB;
}

vector<vector<int>> devise_strategy(int n) {
  vector<vector<int>> strategy(23, vector<int>(n + 1));
  for (int pos = 0; pos < 8; pos++) {
    for (int digit = 0; digit < 3; digit++) {
      int num = get_num(digit, pos);
      if (num >= 0) strategy[num][0] = whichBag(pos, 0, 1);
    }
  }

  for (int i = 1; i <= n; i++) {
    string cur = base3(i);
    strategy[0][i] = get_num(cur[0] - '0', 0);
    for (int pos = 0; pos < 8; pos++) {
      int thisDigit = cur[pos] - '0';
      for (int digit = 0; digit < 3; digit++) {
        int num = get_num(digit, pos);
        if (num >= 0) {
          if (thisDigit > digit)
            strategy[num][i] = whichBag(pos, -2,-1);
          else if (thisDigit < digit)
            strategy[num][i] = whichBag(pos, -1, -2);
          else if (thisDigit == digit && pos != 7) {
            strategy[num][i] = get_num(cur[pos + 1] - '0', pos + 1);
            if (pos == 6) {
              if(cur[pos + 1] - '0' == 0){ strategy[num][i] = -2; continue; }
              else if(cur[pos + 1] - '0' == 2) { strategy[num][i] = -1; continue; }
            }
          }
        }
      }
    }
  }

  // for(auto& v : strategy){
  //   for(auto& x : v) cout << x << " ";
  //   cout << endl;
  // }


  return strategy;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
70.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Partially correct 1 ms 212 KB Output is partially correct
3 Partially correct 1 ms 212 KB Output is partially correct
4 Partially correct 8 ms 596 KB Output is partially correct
5 Partially correct 14 ms 852 KB Output is partially correct
6 Partially correct 11 ms 1020 KB Output is partially correct
7 Partially correct 11 ms 980 KB Output is partially correct
8 Partially correct 0 ms 212 KB Output is partially correct
9 Partially correct 1 ms 340 KB Output is partially correct
10 Partially correct 2 ms 340 KB Output is partially correct
11 Partially correct 5 ms 504 KB Output is partially correct
12 Partially correct 10 ms 852 KB Output is partially correct