Submission #727246

#	Time	Username	Problem	Language	Result	Execution time	Memory
727246		fuad27	Prisoner Challenge (IOI22_prison)	C++17	42.50 / 100	485 ms	2056 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
int base=3, lg=0;
void calc(int N){
  long long pw=base;
  while(pw<=N) {
    pw*=base;
    lg++;
  }
}
struct S {
  int idx,  val;
  S(){}
  S(int v) {
    val=v%(base+1);
    idx=v/(base+1);
  }
};
int toInt(S s) {
  return s.idx*(base+1)+s.val;
}
int getB(int n, int idx) {
  vector<int> v;
  for(int i = 0;i<=lg;i++) {
    v.push_back(n%base);
    n/=base;
  }
  reverse(v.begin(),v.end());
  return v[idx];
}
std::vector<std::vector<int>> devise_strategy(int N) {
  lg++;
  calc(N);
  int X=lg*(base+1)+base;
  cerr << X << endl;
  vector<vector<int>> s(X+1, vector<int> (N+1));
  for(int i = 0;i<=X;i++) {
    S wh=S(i);
    if(wh.idx%2==0) {
      s[i][0]=0;
    }
    else {
      s[i][0]=1;
    }
    cerr << s[i][0] << " ";
    for(int sz=1;sz<=N;sz++) {
      int val=getB(sz, wh.idx);
      if(val<wh.val) {
        if(wh.idx%2==0) {
          s[i][sz]=-1;
        }
        else s[i][sz]=-2;
      }
      else if(val>wh.val) {
        if(wh.idx%2==0) {
          s[i][sz]=-2;
        }
        else s[i][sz]=-1;
      }
      else if(wh.idx==lg) {
        s[i][sz]=-1; 
      }
      else {
        S res;
        res.val=getB(sz,wh.idx+1);
        res.idx=wh.idx+1;
        s[i][sz]=toInt(res);
      }
      cerr << s[i][sz] << " ";
    }
    cerr << endl;
  }
  return s;
}
 

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