| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 903578 |
2024-01-11T08:55:23 Z |
phoebe |
Parrots (IOI11_parrots) |
C++17 |
|
8 ms |
1436 KB |
#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;
}
#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
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;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1304 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1316 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1320 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1328 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1336 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1296 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1320 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1324 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1332 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1328 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1320 KB |
Output is correct - P = 4.750000 |
| 2 |
Correct |
3 ms |
1324 KB |
Output is correct - P = 4.750000 |
| 3 |
Correct |
4 ms |
1328 KB |
Output is correct - P = 4.757576 |
| 4 |
Correct |
6 ms |
1348 KB |
Output is correct - P = 4.760000 |
| 5 |
Correct |
7 ms |
1360 KB |
Output is correct - P = 4.766667 |
| 6 |
Correct |
8 ms |
1360 KB |
Output is correct - P = 4.777778 |
| 7 |
Correct |
8 ms |
1372 KB |
Output is correct - P = 4.750000 |
