Submission #811248

#	Time	Username	Problem	Language	Result	Execution time	Memory
811248		blackyuki	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	10 ms	1148 KiB

prison

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001001001;

std::vector<std::vector<int>> devise_strategy(int N){
    vi tmp={2,2,2,2,2,3,3,3,6};
    vector<vector<int>> res(1);
    res[0].pb(0);
    ll m=1;
    {
        ll prod=1;
        REP(k,1,tmp.size())prod*=tmp[k];
        rep(j,N)res[0].pb(m+j/prod%tmp[0]);
        m+=tmp[0];
    }
    REP(i,1,tmp.size()){
        vector<vector<int>> v(tmp[i-1]);
        ll prod1=1,prod2=1;
        REP(k,i,tmp.size())prod1*=tmp[k];
        REP(k,i+1,tmp.size())prod2*=tmp[k];
        rep(k,tmp[i-1])v[k].pb(i%2);
        rep(k,tmp[i-1])rep(j,N){
            ll t=j/prod1%tmp[i-1];
            if(k==t){
                if(i==tmp.size()-1)v[k].pb(m+j/prod2%tmp[i]/2);
                else v[k].pb(m+j/prod2%tmp[i]);
            }
            else if((k<t)^(i%2))v[k].pb(-2);
            else v[k].pb(-1);
        }
        rep(k,tmp[i-1])res.pb(v[k]);
        m+=tmp[i];
    }
    rep(k,3){
        vector<int> v;
        v.pb(tmp.size()%2);
        rep(j,N){
            ll r=j%6;
            if(r/2==k){
                if((r+tmp.size())%2)v.pb(-2);
                else v.pb(-1);
            }
            else if((k<r/2)^(tmp.size()%2))v.pb(-2);
            else v.pb(-1);
        }
        res.pb(v);
    }
    return res;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:42:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                 if(i==tmp.size()-1)v[k].pb(m+j/prod2%tmp[i]/2);
      |                    ~^~~~~~~~~~~~~~

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