Submission #727301

#	Time	Username	Problem	Language	Result	Execution time	Memory
727301		vjudge1	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	53 ms	1012 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