Submission #859177

#	Time	Username	Problem	Language	Result	Execution time	Memory
859177		kim	Prisoner Challenge (IOI22_prison)	C++17	56 / 100	13 ms	1800 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
//#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back

//#define int ll

const int md=1e9+7;
const int inf=1e9+7;

vector<vector<int>> ans(61);
int n;

void playB(int ii,int al,int ar,int bl,int br);
void playA(int ii,int al,int ar,int bl,int br){
    if(al==ar&&bl==br) return;
    ans[ii][0]=0;
    int mid=al+(ar-al>>1);
    for(int i=al;i<=ar;++i){
        if(i>br) ans[ii][i]=-2;
        else if(i<bl) ans[ii][i]=-1;
    }
    n=max(n,ii+1);
    if(bl==br) return;
    mid=bl+(br-bl>>1);
    int temp=ii+1;
    if(ii%2==1) temp+=2;
    for(int i=bl;i<=mid;++i) ans[ii][i]=ii+2;
    for(int i=mid+1;i<=br;++i) ans[ii][i]=temp;
    playB(ii+2,bl,mid,bl,br);
    playB(temp,mid+1,br,bl,br);
}
void playB(int ii,int al,int ar,int bl,int br){
    if(al==ar&&bl==br) return;
    ans[ii][0]=1;
    int mid=bl+(br-bl>>1);
    for(int i=bl;i<=br;++i){
        if(i>ar) ans[ii][i]=-1;
        else if(i<al) ans[ii][i]=-2;
    }
    n=max(n,ii+1);
    if(al==ar) return;
    mid=al+(ar-al>>1);
    int temp=ii+1;
    if(ii%2==1) temp+=2;
    for(int i=al;i<=mid;++i) ans[ii][i]=ii+2;
    for(int i=mid+1;i<=ar;++i) ans[ii][i]=temp;
    playA(ii+2,al,ar,al,mid);
    playA(temp,al,ar,mid+1,ar);
}

vector<vector<int>> devise_strategy(int N){
    ans.resize(64);
    for(auto &e:ans) e.resize(N+1);
    n=0;
    int mid=1+(N-1>>1);
    for(int i=1;i<=mid;++i){
        ans[0][i]=1;
    }
    for(int i=mid+1;i<=N;++i) ans[0][i]=2;

    playB(1,1,mid,1,N);
    playB(2,mid+1,N,1,N);
//    cout<<n<<" ====="<<endl;
    ans.resize(n);
    return ans;
}

Compilation message (stderr)

prison.cpp: In function 'void playA(int, int, int, int, int)':
prison.cpp:23:19: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   23 |     int mid=al+(ar-al>>1);
      |                 ~~^~~
prison.cpp:30:15: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   30 |     mid=bl+(br-bl>>1);
      |             ~~^~~
prison.cpp: In function 'void playB(int, int, int, int, int)':
prison.cpp:41:19: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   41 |     int mid=bl+(br-bl>>1);
      |                 ~~^~~
prison.cpp:48:15: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   48 |     mid=al+(ar-al>>1);
      |             ~~^~~
prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:61:17: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   61 |     int mid=1+(N-1>>1);
      |                ~^~

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