Submission #926173

#	Time	Username	Problem	Language	Result	Execution time	Memory
926173		hotboy2703	Parrots (IOI11_parrots)	C++17	100 / 100	10 ms	1604 KiB

encoder

#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);
    }

}

decoder

#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 (stderr)

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 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 19 / 19