| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 549568 | PunnyBunny | Parrots (IOI11_parrots) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(int n, int vc[]) {
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);
}#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
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(int n, int m, int vc[]) {
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 i : vc) {
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]);
}