oj.uz

Submission #903602

# Submission time Handle Problem Language Result Execution time Memory
903602 2024-01-11T10:00:59 Z phoebe Parrots (IOI11_parrots) C++17
52 / 100
 8 ms 1520 KB 
#include <bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
using namespace std;
 
#define ll unsigned long long
 
static const int maxx = 31;
static ll idx, dp[40][32] = {0};
static int v[6], sz;
 
static ll _pow(ll n, ll e){
    ll re = 1ll;
    while (e){
        if (e&1) re *= n;
        n *= n;
        e /= 2;
    }
    return re;
}

// 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;
//     }
//     return re;
// }
 
ll raw_to_hash(){
    ll re = 0;
    for (int i = 0; i < sz; i++){
        int rem_length = sz - i - 1;
        ll bruh = v[i] * _pow(256, rem_length);
        re += bruh;
    }
    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 bruh_encode(int i, ll rem, int last){
    while (i){
        for (int y = last; y <= maxx; y++){
            ll cnt = dp[i - 1][y];
            if (rem >= cnt) rem -= cnt;
            else{
                send(idx + y); 
                last = y; i--;
                break;
            }
        }
    }
}
 
void encode(int N, int M[]){
    dp_encode();
    int angie = 0;
    for (int i = 0; i < N; i += 8){
        idx = angie<<5; angie++;
        // vector<int> v;
        sz = 0;
        for (int j = i; j < min(N, i + 8); j++){
            // v.push_back(M[j]);
            v[sz++] = M[j];
        }
        // ll hash = raw_to_hash(v);
        ll hash = raw_to_hash();
        // actually_encode(min((int)v.size() * 5, (int)38), hash, 0);
        bruh_encode(min((int)sz * 5, (int)38), hash, 0);
    }
}
#include <bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"
using namespace std;
 
#define ll unsigned long long
 
static const int maxx = 31;
static ll dp[40][32] = {0};
static int v[6], sz;

static ll _pow(ll n, ll e){
    ll re = 1ll;
    while (e){
        if (e&1) re *= n;
        n *= n;
        e /= 2;
    }
    return re;
}

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){
    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;
        output(y);
        rem %= bruh;
        angie += y * bruh;
    }
}

void decode(int N, int L, int X[]){
    dp_decode();
    sort(X, X + L); 
    for (int i = 0; i < L; i += 38){
        // vector<int> v;
        sz = 0;
        for (int j = i; j < min(L, i + 38); j++){
            // v.push_back(X[j] % 32);
            v[sz++] = (X[j] & ((1<<5) - 1));
            // v[sz++] = X[j] % 32;
        }
        ll hash = 0;
        ll angie = 0;
        for (int j = 0; j < sz; j++){
            int heh = sz - j - 1;
            for (int x = (j == 0 ? 0 : v[j - 1]); x < v[j]; x++){
                hash += dp[heh][x];
            }
        }
        actually_decode((sz + 4) / 5, hash);
    }
}

Compilation message

decoder.cpp: In function 'long long unsigned int cnt_decode(int, int)':
decoder.cpp:23:18: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   23 |     if (dp[i][x] != -1) return dp[i][x];
      |         ~~~~~~~~~^~~~~
decoder.cpp: In function 'void actually_decode(int, long long unsigned int)':
decoder.cpp:43:19: warning: unused variable 'og_rem' [-Wunused-variable]
   43 |     ll angie = 0, og_rem = rem;
      |                   ^~~~~~
decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:66:12: warning: unused variable 'angie' [-Wunused-variable]
   66 |         ll angie = 0;
      |            ^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1332 KB Output is correct
2 Correct 2 ms 1344 KB Output is correct
3 Correct 3 ms 1340 KB Output is correct
4 Correct 3 ms 1340 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1340 KB Output is correct
2 Correct 4 ms 1344 KB Output is correct
3 Correct 3 ms 1348 KB Output is correct
4 Correct 3 ms 1340 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1372 KB Output is correct
2 Correct 3 ms 1340 KB Output is correct
3 Incorrect 3 ms 1344 KB Error : Output is wrong
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1284 KB Output is correct - P = 4.750000
2 Correct 5 ms 1336 KB Output is correct - P = 4.750000
3 Incorrect 2 ms 1332 KB Error : Output is wrong
4 Incorrect 4 ms 1368 KB Error : Output is wrong
5 Correct 7 ms 1368 KB Output is correct - P = 4.766667
6 Correct 6 ms 1376 KB Output is correct - P = 4.777778
7 Correct 8 ms 1520 KB Output is correct - P = 4.750000