| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 389420 | quickn | Parrots (IOI11_parrots) | C++14 | 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.
using namespace std;
typedef long long i64;
const int MAX_LENGTH = 40;
vector<pair<int, int>> list(N, make_pair(0, 0));
for (int i = 0; i < N; i++) {
list[i] = make_pair(M[i], i);
}
vector<i64> msg_block;
for (int i = 0; i < N/8; i++) {
i64 msg = 0;
for (int j = 0; j < 8; j++) {
msg = msg*256 + static_cast<i64>(list[i*8 + j].first);
}
msg_block.push_back(msg);
}
i64 msg = 0;
for (int i = 8*(N/8); i < N; i++) {
msg = msg*256 + static_cast<i64>(list[i].first);
}
if (N % 8 != 0)
msg_block.push_back(msg);
vector<vector<i64>> dp(MAX_LENGTH, vector<i64>(32, 0));
for (int j = 0; j < 32; j++)
dp[0][j] = 1;
for (int i = 1; i < MAX_LENGTH; i++) {
for (int j = 0; j < 32; j++)
if (j > 0)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
else
dp[i][j] = dp[i-1][j];
}
int cnt = 0;
vector<int> q;
for (auto msg: msg_block) {
i64 m = msg;
int i = MAX_LENGTH-1;
int j = 30;
vector<int> arr;
while (i >= 0) {
bool non = false;
while (m > 0 && j > 0) {
if (dp[i][j-1] == m) {
m -= dp[i][j-1];
arr.push_back(j);
non = true;
break;
} else if (dp[i][j-1] < m) {
m -= dp[i][j-1];
arr.push_back(j+1);
non = true;
break;
}
j--;
}
if (!non) { arr.push_back(0); }
i--;
}
for (auto a: arr) {
send(cnt*32 + a);
}
cnt += 1;
}
using namespace std;
typedef long long i64;
const int MAX_LENGTH = 40;
vector<vector<i64>> dp(MAX_LENGTH, vector<i64>(32, 0));
for (int j = 0; j < 32; j++)
dp[0][j] = 1;
for (int i = 1; i < MAX_LENGTH; i++) {
for (int j = 0; j < 32; j++)
if (j > 0)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
else
dp[i][j] = dp[i-1][j];
}
vector<vector<int>> recover(static_cast<int>(ceil(static_cast<long double>(N)/8.0)));
for (int i = 0; i < L; i++) {
recover[X[i] / 32].push_back(X[i] % 32);
}
for (int i = 0; i < recover.size(); i++) {
sort(recover[i].begin(), recover[i].end(), greater<int>());
i64 nth = 0;
for (int j = 0; j < recover[i].size(); j++) {
if (recover[i][j] == 0)
break;
if (j == recover[i].size()-1 || recover[i][j+1] == 0) {
nth += dp[recover[i].size()-j-1][recover[i][j]-1];
} else {
nth += dp[recover[i].size()-j-1][recover[i][j]-2];
}
}
vector<int> out;
if (i == recover.size()-1 && N % 8 != 0) {
for (int j = 8*(N/8); j < N; j++) {
out.push_back(nth % 256);
nth /= 256;
}
} else {
for (int j = 0; j < 8; j++) {
out.push_back(nth % 256);
nth /= 256;
}
}
for (int j = out.size()-1; j >= 0; j--)
output(out[j]);// out[j] << " ";
}