Submission #903578

#	Time	Username	Problem	Language	Result	Execution time	Memory
903578		phoebe	Parrots (IOI11_parrots)	C++17	100 / 100	8 ms	1436 KiB

encoder

#include <bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
using namespace std;
 
#pragma optimize "03"

#define ll unsigned long long
 
static const int maxx = 31;
static ll idx, dp[40][32] = {0};
 
ll raw_to_hash(vector<int> &v){
    ll re = 0;
    for (int i = 0; i < v.size(); i++){
        int rem_length = v.size() - i - 1;
        ll bruh = v[i] * pow(256, rem_length);
        re += bruh;
        // re += v[i] * pow(256, rem_length);
        // cout << v[i] * pow(256, rem_length) << endl;
        // cout << re << endl;
    }
    return re;
}
 
ll cnt_encoded(int i, int x){
    if (dp[i][x] != -1) return dp[i][x];
    if (i == 0) return 1ll;
    ll re = 0;
    for (int y = x; y <= maxx; y++) re += cnt_encoded(i - 1, y);
    dp[i][x] = re;
    return re;
}
 
void dp_encode(){
    for (int x = 0; x < 32; x++) dp[0][x] = 1;
    for (int i = 1; i < 40; i++){
        for (int x = 0; x < 32; x++){
            ll re = 0;
            for (int y = x; y <= maxx; y++) re += dp[i - 1][y];
            dp[i][x] = re;
        }
    }
}

void actually_encode(int i, ll rem, int last){
    // cout << i << ' ' << rem << ' ' << last << endl;
    if (i == 0) return;
    for (int y = last; y <= maxx; y++){
        // ll cnt = cnt_encoded(i - 1, y);
        ll cnt = dp[i - 1][y];
        if (rem >= cnt) rem -= cnt;
        else{
            send(idx + y);
            // cout << y << ' ';
            actually_encode(i - 1, rem, y);
            return;
        }
        // cout << rem << endl;
        // cout << rem << ' ' << cnt << endl;
    }
}
 
void encode(int N, int M[]){
    // fill(&dp[0][0], &dp[0][0] + 40 * 32, -1);
    dp_encode();
    int angie = 0;
    for (int i = 0; i < N; i += 8){
        idx = angie<<5; angie++;
        vector<int> v;
        for (int j = i; j < min(N, i + 8); j++){
            v.push_back(M[j]);
        }
        // for (auto k : v) cout << k << ' '; cout << endl;
        ll hash = raw_to_hash(v);
        // cout << "encoder hash: " << hash << endl;
        actually_encode(min((int)v.size() * 5, (int)38), hash, 0);
        // cout << endl;
    }
    // cout << endl << endl;
}

decoder

#include <bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"
using namespace std;
 
#pragma optimize "03"

#define ll unsigned long long
 
static const int maxx = 31;
static ll dp[40][32] = {0};
 
ll cnt_decode(int i, int x){
    if (dp[i][x] != -1) return dp[i][x];
    if (i == 0) return 1ll;
    ll re = 0;
    for (int y = x; y <= maxx; y++) re += dp[i - 1][y];
    dp[i][x] = re;
    return re;
}
 
void dp_decode(){
    for (int x = 0; x < 32; x++) dp[0][x] = 1;
    for (int i = 1; i < 40; i++){
        for (int x = 0; x < 32; x++){
            ll re = 0;
            for (int y = x; y <= maxx; y++) re += dp[i - 1][y];
            dp[i][x] = re;
        }
    }
}

void actually_decode(int i, ll rem){
    // cout << "this is i: " << i << endl;
    ll angie = 0, og_rem = rem;
    for (int j = 0; j < i; j++){
        int rem_length = i - j - 1;
        ll bruh = pow(256, rem_length);
        ll y = rem / bruh;
        // cout << y << ' ';
        output(y);
        rem %= bruh;
        angie += y * bruh;
        // cout << angie << endl;
    }
}
 
void decode(int N, int L, int X[]){
    dp_decode();
    // fill(&dp[0][0], &dp[0][0] + 40 * 32, -1);
    sort(X, X + L); 
    // for (int i = 0; i < L; i++) cout << X[i] << ' '; cout << endl;
    for (int i = 0; i < L; i += 38){
        vector<int> v;
        for (int j = i; j < min(L, i + 38); j++){
            v.push_back(X[j] % 32);
        }
        // for (auto k : v) cout << k << ' '; cout << endl;
        ll hash = 0;
        ll angie = 0;
        for (int j = 0; j < v.size(); j++){
            int sz = v.size() - j - 1;
            for (int x = (j == 0 ? 0 : v[j - 1]); x < v[j]; x++){
                // hash += cnt_decode(sz, x);
                hash += dp[sz][x];
            }
        }
        // cout << "decoder hash: " << hash << endl;
        actually_decode((v.size() + 4) / 5, hash);
        // cout << endl;
    }
}

Compilation message (stderr)

encoder.cpp:6: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    6 | #pragma optimize "03"
      | 
encoder.cpp: In function 'long long unsigned int raw_to_hash(std::vector<int>&)':
encoder.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i = 0; i < v.size(); i++){
      |                     ~~^~~~~~~~~~
encoder.cpp: In function 'long long unsigned int cnt_encoded(int, int)':
encoder.cpp:27:18: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   27 |     if (dp[i][x] != -1) return dp[i][x];
      |         ~~~~~~~~~^~~~~

decoder.cpp:6: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    6 | #pragma optimize "03"
      | 
decoder.cpp: In function 'long long unsigned int cnt_decode(int, int)':
decoder.cpp:14:18: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   14 |     if (dp[i][x] != -1) return dp[i][x];
      |         ~~~~~~~~~^~~~~
decoder.cpp: In function 'void actually_decode(int, long long unsigned int)':
decoder.cpp:35:19: warning: unused variable 'og_rem' [-Wunused-variable]
   35 |     ll angie = 0, og_rem = rem;
      |                   ^~~~~~
decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int j = 0; j < v.size(); j++){
      |                         ~~^~~~~~~~~~
decoder.cpp:60:12: warning: unused variable 'angie' [-Wunused-variable]
   60 |         ll angie = 0;
      |            ^~~~~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 19 / 19