Submission #727297

#	Time	Username	Problem	Language	Result	Execution time	Memory
727297		fuad27	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	34 ms	980 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) {
    v--;
    val=v%(base);
    idx=v/(base);
    if(idx==lg)val++;
  }
};
int toInt(S s) {
  return s.idx*(base)+s.val+1-(s.idx==lg);
}
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) {
  calc(5000);
  int X=lg*(base)+base-2;
  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;
    }
    if(i) {
      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;
          if(res.idx==lg and res.val==2) {
            if(res.idx%2==1)s[i][sz]=-2;
            else s[i][sz]=-1;
          }
          else if(res.idx==lg and res.val==0) {
            if(res.idx%2==1)s[i][sz]=-1;
            else s[i][sz]=-2;
          }
          else s[i][sz]=toInt(res);
        }
      }
    }
    else {
      s[i][0]=1;
      for(int sz=1;sz<=N;sz++) {
        S res;
        res.val=getB(sz,wh.idx);
        res.idx=0;
        s[i][sz]=toInt(res);
      }
    }
  }
  return s;
}

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