Submission #549573

#	Time	Username	Problem	Language	Result	Execution time	Memory
549573		PunnyBunny	Parrots (IOI11_parrots)	C++17	99 / 100	10 ms	1388 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
 
#include <bits/stdc++.h>
 
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
int nxt() {
    int t;
    cin >> t;
    return t;
}
int dp[17][20];
vector<int> encode(int x) {
    vector<int> res(20);
    for (int j = 19; j >= 0; --j) {
        for (int i = 0; i < 17; ++i) {
            if (x - dp[i][j] < 0) {
                res[j] = i;
                break;
            }
            x -= dp[i][j];
        }
    }
    while (res.back() == 16) res.pop_back();
    return res;
}
void encode(int32_t n, int32_t vc[]) {memset(dp,0,sizeof dp);
  for (int i = 0; i < 17; ++i) dp[i][0] = 1;
    for (int j = 1; j < 20; ++j) {
        for (int i = 0; i < 17; ++i) {
            for (int k = 0; k <= i; ++k) {
                dp[i][j] += dp[k][j - 1];
            }
        }
    }
  vector<int> v(vc, vc+n);
   while (n % 4) {
                v.push_back(0);
                ++n;
            }
 
            vector<int> ans;
            for (int i = 0; i < n; i += 4) {
                auto x = encode((v[i] << 24) + (v[i + 1] << 16) + (v[i + 2] << 8) + v[i + 3]);
                for (int j : x) ans.push_back(((i / 4) << 4) + j);
            }
  for (int i : ans) send(i);
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
int nxt() {
    int t;
    cin >> t;
    return t;
}
int dp[17][20];
int decode(vector<int> x) {
    sort(all(x));
    while (x.size() < 20) x.push_back(16);
 
    int res = 0;
    for (int j = 0; j < 20; ++j) {
        for (int i = 1; i < 17; ++i) {
            if (x[j] >= i) res += dp[i - 1][j];
        }
    }
    return res;
}
void decode(int32_t n, int32_t m, int32_t vc[]) {memset(dp, 0,sizeof dp);
  for (int i = 0; i < 17; ++i) dp[i][0] = 1;
    for (int j = 1; j < 20; ++j) {
        for (int i = 0; i < 17; ++i) {
            for (int k = 0; k <= i; ++k) {
                dp[i][j] += dp[k][j - 1];
            }
        }
    }
  
  vector<int> u[16];
            for (int j = 0; j < m; ++j) {
              int i = vc[j];
                int idx = i >> 4;
                u[idx].push_back(i & 15);
            }
            vector<int> ans;
            for (auto x : u) {  // n!
                if (x.empty()) continue;
                int y = decode(x);
                ans.push_back(y >> 24);
                ans.push_back(y >> 16 & 255);
                ans.push_back(y >> 8 & 255);
                ans.push_back(y & 255);
            }
            for (int i = 0; i < n; ++i) output(ans[i]);
  
}

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