oj.uz

Submission #926173

# Submission time Handle Problem Language Result Execution time Memory
926173 2024-02-12T16:31:14 Z hotboy2703 Parrots (IOI11_parrots) C++17
100 / 100
 10 ms 1604 KB 
#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using ll = __int128_t;
using ull = unsigned long long;
using ld = long double;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
const ll BATCH = 8;
namespace {

    ll dp[BATCH*5+1][BATCH*4+1];
    void init(){
        dp[0][0] = 1;
        for (ll k = 1;k <= BATCH*4;k ++)dp[0][k] = 1;
        for (ll n = 1;n <= BATCH*5;n ++)dp[n][0] = 0;
        for (ll n = 1;n <= BATCH*5;n ++){
            for (ll k = 1;k <= BATCH*4;k ++){
                dp[n][k] = 0;
                for (ll j = 0;j <= n;j ++){
                    dp[n][k] += dp[j][k-1];
                }
            }
        }
    }
    vector <ll> chia_keo(ll n,ll k,ll x){
        //chia n keo cho k cai ro, cach thu x la gi
        vector <ll> res(k);
        while (k--){
            for (ll i = 0;i <= n;i ++){
                if (dp[n-i][k] <= x)x -= dp[n-i][k];
                else{
                    res[k] = i;
                    n -= i;
                    break;
                }
            }
        }
        return res;
    }
    ll rev(ll n,ll k,vector <ll> res){
        ll ans = 0;
        for (ll i = k - 1;i >= 0;i --){
            for (ll j = 0;j < res[i];j ++){
                ans += dp[n-j][i];
            }
            n -= res[i];
        }
        return ans;
    }
}
void encode(int N, int M[])
{
    init();
    vector <ll> a((N+BATCH-1)/BATCH*BATCH);
    vector <ll> res(300);
    for (ll i = 0;i < N;i ++)a[i]=M[i];
    for (ll i = 0;i < N;i += BATCH){
        ll x = 0;
        for (ll j = 0;j < BATCH;j ++)x += a[i+j]<<(j*8);
        if (N-i<=BATCH){
//            cout<<"OK"<<endl;
            ll y = BATCH;
            vector <ll> tmp = chia_keo(5*(N-i),4*y,x);
            for (ll j = 0;j < 4*y;j ++)res[j+i*4]=tmp[j];
        }
        else{
            vector <ll> tmp = chia_keo(BATCH*5,BATCH*4,x);
            for (ll j = 0;j < BATCH*4;j ++)res[j+i*4]=tmp[j];
        }
    }
    for (ll i = 0;i < 256;i ++){
        while (res[i]--)send(i);
    }

}

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using ll = __int128_t;
using ull = unsigned long long;
using ld = long double;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
const ll BATCH = 8;
namespace {

    ll dp[BATCH*5+1][BATCH*4+1];
    void init(){
        dp[0][0] = 1;
        for (ll k = 1;k <= BATCH*4;k ++)dp[0][k] = 1;
        for (ll n = 1;n <= BATCH*5;n ++)dp[n][0] = 0;
        for (ll n = 1;n <= BATCH*5;n ++){
            for (ll k = 1;k <= BATCH*4;k ++){
                dp[n][k] = 0;
                for (ll j = 0;j <= n;j ++){
                    dp[n][k] += dp[j][k-1];
                }
            }
        }
    }
    vector <ll> chia_keo(ll n,ll k,ll x){
        //chia n keo cho k cai ro, cach thu x la gi
        vector <ll> res(k);
        while (k--){
            for (ll i = 0;i <= n;i ++){
                if (dp[n-i][k] <= x)x -= dp[n-i][k];
                else{
                    res[k] = i;
                    n -= i;
                    break;
                }
            }
        }
        return res;
    }
    ll rev(ll n,ll k,vector <ll> res){
        ll ans = 0;
        for (ll i = k - 1;i >= 0;i --){
            for (ll j = 0;j < res[i];j ++){
                ans += dp[n-j][i];
            }
            n -= res[i];
        }
        return ans;
    }
}
void decode(int N, int L, int X[])
{
    init();
    vector <ll> res(300);
    for (ll i = 0;i < L;i ++){
        res[X[i]]++;
    }
    vector <ll> a((N+BATCH-1)/BATCH*BATCH);
    for (ll i = 0;i < N;i += BATCH){
        vector <ll> tmp(BATCH*4);
        for (ll j = 0;j < BATCH*4;j ++){
            tmp[j] = res[i*4+j];
        }
        if (N-i<=BATCH){
            ll y = BATCH;
            ll x = rev(5*(N-i),4*y,tmp);
            for (ll j = 0;j < BATCH;j ++)a[i+j] = (x>>(j*8)) & (MASK(8)-1);
        }
        else{
            ll x = rev(BATCH*5,BATCH*4,tmp);
            for (ll j = 0;j < BATCH;j ++)a[i+j] = (x>>(j*8)) & (MASK(8)-1);
        }
    }
    for (ll i = 0;i < N;i++)output(a[i]);
}

Compilation message

encoder.cpp:47:8: warning: 'll {anonymous}::rev(ll, ll, std::vector<__int128>)' defined but not used [-Wunused-function]
   47 |     ll rev(ll n,ll k,vector <ll> res){
      |        ^~~

decoder.cpp:32:17: warning: 'std::vector<__int128> {anonymous}::chia_keo(ll, ll, ll)' defined but not used [-Wunused-function]
   32 |     vector <ll> chia_keo(ll n,ll k,ll x){
      |                 ^~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 780 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1296 KB Output is correct
2 Correct 3 ms 1312 KB Output is correct
3 Correct 4 ms 1308 KB Output is correct
4 Correct 4 ms 1320 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1304 KB Output is correct
2 Correct 3 ms 1312 KB Output is correct
3 Correct 5 ms 1308 KB Output is correct
4 Correct 4 ms 1320 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1304 KB Output is correct
2 Correct 4 ms 1316 KB Output is correct
3 Correct 5 ms 1312 KB Output is correct
4 Correct 5 ms 1328 KB Output is correct
5 Correct 5 ms 1328 KB Output is correct
6 Correct 5 ms 1332 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1312 KB Output is correct
2 Correct 5 ms 1328 KB Output is correct
3 Correct 5 ms 1332 KB Output is correct
4 Correct 10 ms 1604 KB Output is correct
5 Correct 8 ms 1352 KB Output is correct
6 Correct 8 ms 1368 KB Output is correct
7 Correct 8 ms 1364 KB Output is correct