Submission #727215

#	Time	Username	Problem	Language	Result	Execution time	Memory
727215		fuad27	Prisoner Challenge (IOI22_prison)	C++17	30 / 100	39 ms	1668 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
int base=4, lg=0;
void calc(int N){
  long long pw=base;
  while(pw<=N) {
    pw*=base;
    lg++;
  }
}
struct S {
  int idx, val;
  S(){}
  S(int I) {
    val=I%(base+2); 
    idx=(I-val)/(base+2);
    idx=max(0, lg-idx);
  }
};
int toInt(S s) {
  if(s.val<0)return s.val;
  s.idx=lg-s.idx;
  return s.idx*(base+2)+s.val;
}
int ask(S num) {
  if(num.val==0) {
    return 1;
  }
  return 0;
}
int getB(int val, int idx) {
  vector<int> v;
  for(int i=0;i<=idx;i++) {
    v.push_back(val%base);
    val/=base;
  }
  return v[idx];
}
S askC(S num, int val) {
  if(num.val==0) {
      S nn;
      nn.idx=num.idx;
      nn.val=getB(val, num.idx)+1;
      return nn;
  }
  else {
    S nn;
    nn.idx=num.idx-1;
    nn.val=getB(val, num.idx)+1;
    if(nn.val>num.val)nn.val=-2;
    else if(nn.val<num.val)nn.val=-1;
    else nn.val=0;
    if(nn.idx<0 and nn.val==0)nn.val=-2;
    return nn;
  }
}
std::vector<std::vector<int>> devise_strategy(int N) {
  calc(N);
  int X=lg*(base+2)+base+1;
  cerr << X << endl;
  vector<vector<int>> s(X+1, vector<int> (N+1));
  for(int i = 0;i<=X;i++) {
    s[i][0]=ask(S(i));
//    cerr << s[i][0] << " ";
    for(int val=1;val<=N;val++) {
      s[i][val]=toInt(askC(S(i), val));
//      cerr << s[i][val] << " ";
    }
//    cerr << endl;
  }
  return s;
}

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