oj.uz

답안 #812145

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
812145 2023-08-07T07:29:33 Z blackyuki 죄수들의 도전 (IOI22_prison) C++17
100 / 100
 13 ms 1108 KB 
#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';}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
const ll inf=1001001001001001001;

std::vector<std::vector<int>> devise_strategy(int N){
    vi tmp={2,3,3,3,3,2,2,2,2};
    vi tmp2={5022,2510,836,278,92,30,14,6,2};
    auto f=[&](ll x,ll i){
        rep(j,i)x=(x-1)%tmp2[j+1];
        if(x==0)return -1ll;
        if(x==tmp2[i]-1)return -2ll;
        return (x-1)/(tmp2[i+1]);
    };
    vector<vector<int>> res(1);
    res[0].pb(0);
    ll m=1;
    {
        rep(j,N){
            ll x=f(j,0);
            if(x==-1)res[0].pb(-1);
            else if(x==-2)res[0].pb(-2);
            else res[0].pb(m+x);
        }
        m+=tmp[0];
    }
    REP(i,1,tmp.size()){
        vector<vector<int>> v(tmp[i-1]);
        rep(k,tmp[i-1])v[k].pb(i%2);
        rep(k,tmp[i-1])rep(j,N){
            ll x=f(j,i-1);
            if(x==-1)v[k].pb(-1-i%2);
            else if(x==-2)v[k].pb(-2+i%2);
            else if(k<x)v[k].pb(-2+i%2);
            else if(k>x)v[k].pb(-1-i%2);
            if(k==x){
                ll y=f(j,i);
                if(y==-1)v[k].pb(-1-i%2);
                else if(y==-2)v[k].pb(-2+i%2);
                else v[k].pb(m+y);
            }
        }
        rep(k,tmp[i-1])res.pb(v[k]);
        m+=tmp[i];
    }
    return res;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 308 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
90.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 5 ms 592 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 11 ms 1068 KB Output is correct
7 Correct 11 ms 1108 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 13 ms 852 KB Output is correct