Submission #697197

#	Time	Username	Problem	Language	Result	Execution time	Memory
697197		FEDIKUS	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	70 ms	980 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>
#include <vector>

using namespace std;

const int maxn=5010;

int dp[maxn];
int od[maxn];
int del[maxn];
pair<int,int> rasponx[50];

void napravi(int nivo,int tren,int tx,pair<int,int> ia,pair<int,int> ib,vector<vector<int> > &res){
  res[tx][0]=tren;
  if(tren==0){
    for(int i=ia.first;i<=ia.second;i++){
      if(i<=ib.first) res[tx][i]=-1;
      else if(i>=ib.second) res[tx][i]=-2;
    }
    if(ib.second-ib.first<2) return;
    vector<pair<int,int> > podela;
    int klk=rasponx[nivo].second-rasponx[nivo].first+1;
    int vel=(ib.second-1-ib.first-1)/klk+1;
    int tren=ib.first+1;
    while(tren<=ib.second-1){
      podela.push_back({tren,min(tren+vel-1,ib.second-1)});
      tren+=vel;
    }
    for(int i=ia.first;i<=ia.second;i++){
      if(i<=ib.first) res[tx][i]=-1;
      else if(i>=ib.second) res[tx][i]=-2;
      else{
        for(int j=0;j<(int)podela.size();j++){
          if(podela[j].first<=i && i<=podela[j].second){
            res[tx][i]=rasponx[nivo].first+j;
            break;
          }
        }   
      }
    }
    for(int j=0;j<(int)podela.size();j++){
      napravi(nivo+1,1,rasponx[nivo].first+j,{podela[j].first,podela[j].second},ib,res);
    }
  }else{
    for(int i=ib.first;i<=ib.second;i++){
      if(i<=ia.first) res[tx][i]=-2;
      else if(i>=ia.second) res[tx][i]=-1;
    }
    if(ia.second-ia.first<2) return;
    vector<pair<int,int> > podela;
    int klk=rasponx[nivo].second-rasponx[nivo].first+1;
    int vel=(ia.second-1-ia.first-1)/klk+1;
    int tren=ia.first+1;
    while(tren<=ia.second-1){
      podela.push_back({tren,min(tren+vel-1,ia.second-1)});
      tren+=vel;
    }
    for(int i=ib.first;i<=ib.second;i++){
      if(i<=ia.first) res[tx][i]=-2;
      else if(i>=ia.second) res[tx][i]=-1;
      else{
        for(int j=0;j<(int)podela.size();j++){
          if(podela[j].first<=i && i<=podela[j].second){
            res[tx][i]=rasponx[nivo].first+j;
            break;
          }
        }   
      }
    }
    for(int j=0;j<(int)podela.size();j++){
      napravi(nivo+1,0,rasponx[nivo].first+j,ia,{podela[j].first,podela[j].second},res);
    }
  }
}

vector<vector<int> > devise_strategy(int n) {
  dp[0]=dp[1]=dp[2]=0;
  for(int i=3;i<maxn;i++){
    dp[i]=maxn;
    for(int j=1;j<=i-2;j++){
      dp[i]=min(dp[i],j+dp[(i-3)/j+1]);
      if(dp[i]==j+dp[(i-3)/j+1]){
        od[i]=(i-3)/j+1;
        del[i]=j;
      }
    }
  }
  int tren=n;
  vector<int> klk;
  while(dp[tren]>0){
    klk.push_back(del[tren]);
    tren=od[tren];
  }
  int sum=1;
  for(int i=0;i<(int)klk.size();i++){
    rasponx[i]={sum,sum+klk[i]-1};
    sum+=klk[i];
  }
  vector<vector<int> > res(dp[n]+1,vector<int>(n+1));
  napravi(0,0,0,{1,n},{1,n},res);
  return res;
}

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