oj.uz

Submission #630180

# Submission time Handle Problem Language Result Execution time Memory
630180 2022-08-15T20:50:34 Z CyanForces Prisoner Challenge (IOI22_prison) C++17
90 / 100
 115 ms 1124 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

vector<vi> devise_strategy(int N) {
  cerr << "devise_strategy called with N = " << N << endl;

  auto dividers = [&](int lo, int hi) {
    int stepSize = (hi - lo + 2) / 3;
    int x = lo + stepSize;
    stepSize = (hi - x) / 2;
    return pii(x, x + stepSize);
  };

  vector<vi> strat(4, vi(N+1));
  auto [x, y] = dividers(1, N+1);

  strat[0][0] = 0;
  strat[0][1] = -1;
  strat[0][N] = -2;

  vi options({1,2,3});
  vector<pii> intervals(1,{1,N+1});
  int at = 4;

  rep(i,2,N) {
    int interval = (i >= x) + (i >= y);
    strat[0][i] = options[interval];
  }
  bool checkB = true;

  while(sz(intervals)) {
    //cerr << "new iteration" << endl;
    vector<pii> newIntervals;
    vi newOptions(3,-1);
    pii prev(-1,-1);
    for(auto[lo, hi] : intervals) {
      if (pii(lo, hi) == prev)
        continue;
      prev = pii(lo, hi);
      //cerr << lo << ", " << x << ", " << y << ", " << hi << endl;
      auto [x, y] = dividers(lo, hi);

      rep(prevInterval,0,3) {
        int prev = options[prevInterval];
        if (prev == -1)
          continue;
        while(prev >= sz(strat))
          strat.push_back(vi(N+1));
        strat[prev][0] = checkB;

        rep(resp,lo,N+1) {
          int newInterval = (resp >= x) + (resp >= y);
          if (newInterval > prevInterval) {
            // the answer is in the opposite of what was opened
            strat[prev][resp] = -1-(1-checkB);
            continue;
          }
          else if (newInterval < prevInterval) {
            // the answer is in the current thing that was opened
            strat[prev][resp] = -1-checkB;
            continue;
          }
          // A and B are in the same interval
          //cerr << prev << ", " << resp << ", " << newInterval << endl;
          int newLo = vi({lo+1, x, y})[newInterval];
          int newHi = vi({x, y, hi-1})[newInterval];

          if (resp <= newLo) {
            strat[prev][resp] = -1-checkB;
            //cerr << "a" << endl;
            continue;
          }
          else if (resp >= newHi-1) {
            strat[prev][resp] = -1-(1-checkB);
            //cerr << "b" << endl;
            continue;
          }
          //cerr << "c" << endl;
          auto [newX, newY] = dividers(newLo, newHi);
          int nextInterval = (resp >= newX) + (resp >= newY);
          if (newOptions[nextInterval] == -1) {
            newOptions[nextInterval] = at++;
          }
          newIntervals.push_back({newLo, newHi});
          strat[prev][resp] = newOptions[nextInterval];
        }
      }
    }

    options = newOptions;
    checkB = !checkB;
    intervals = newIntervals;
  }

  /*
  rep(i,0,sz(strat)) {
    cerr << "x = " << i << endl;
    rep(j,0,N+1) {
      cerr << strat[i][j] << " ";
    }
    cerr << endl;
  }
  */
  return strat;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 296 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 1 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 #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 212 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
80.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 20 ms 612 KB Output is correct
5 Partially correct 114 ms 900 KB Output is partially correct
6 Partially correct 115 ms 1124 KB Output is partially correct
7 Partially correct 108 ms 1060 KB Output is partially correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 20 ms 476 KB Output is correct
12 Partially correct 89 ms 904 KB Output is partially correct