oj.uz

Submission #966143

# Submission time Handle Problem Language Result Execution time Memory
966143 2024-04-19T12:25:47 Z andrej246 Prisoner Challenge (IOI22_prison) C++17
48.5 / 100
 14 ms 1372 KB 
#include "prison.h"

#include <bits/stdc++.h>
using namespace std;

#define NL '\n'
#define EL cout << NL
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define FORS(i,s,n) for(int i = (s); i < (n); i++)
#define PRINTV(v) for(auto a:v) {cout << a << " ";} EL;
#define PRINTVV(v) for(auto a:v) {PRINTV(a);}
#define f first
#define s second
#define all(v) (v).begin(),(v).end()
#define STRP(p) "{" << (p).f << "," << (p).s << "}"
#define PRINTVP(v) for(auto a:v) {cout << STRP(a) << " ";} EL;
#define PRINTVVP(v) for(auto a:v) {PRINTVP(a);}

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;

vl pwr;

ll get_trit(ll k, ll n) { // kth least significant trit
    n %= pwr[k+1];
    return n/pwr[k];
}

std::vector<std::vector<int>> devise_strategy(int N) {
    pwr.push_back(1);
    while(pwr.back() <= N) pwr.push_back(3*pwr.back());
    ll mpow = pwr.size()-1;
    ll x = mpow*4-1;
    vector<vector<int>> strat(x+1,vector<int>(N+1));
    FOR(st,mpow) {
        strat[st*4][0] = 0;
        FORS(i,1,N+1) {
            strat[st*4][i] = st*4+1+get_trit(mpow-st-1,i);
        }
        FORS(t,0,3) {
            strat[st*4+t+1][0] = 1;
            FORS(i,1,N+1) {
                ll t2 = get_trit(mpow-st-1,i);
                if (t == t2) strat[st*4+t+1][i] = min((ll)st*4+4,x);
                if (t < t2) strat[st*4+t+1][i] = -1;
                if (t > t2) strat[st*4+t+1][i] = -2;
            }
        }
    }
    //cout << x << NL;
    return strat;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct

Subtask #3
38.5 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Partially correct 6 ms 860 KB Output is partially correct
5 Partially correct 12 ms 1116 KB Output is partially correct
6 Partially correct 14 ms 1372 KB Output is partially correct
7 Partially correct 14 ms 1372 KB Output is partially correct
8 Correct 1 ms 344 KB Output is correct
9 Partially correct 1 ms 348 KB Output is partially correct
10 Partially correct 2 ms 600 KB Output is partially correct
11 Partially correct 5 ms 604 KB Output is partially correct
12 Partially correct 12 ms 1368 KB Output is partially correct