| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 923120 |
2024-02-06T17:18:02 Z |
Lobo |
Parrots (IOI11_parrots) |
C++17 |
|
1264 ms |
24316 KB |
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fr first
#define sc second
#define int long long
// const int maxn = 1e5+10;
// const int inf = 1e18+10;
static int R;
static int k;
static int base = 1e8;
bool geq(vector<int> s, vector<int> t) {
if(s.size() > t.size()) return 1;
if(t.size() > s.size()) return 0;
for(int i = (int) s.size() -1; i >= 0; i--) {
if(s[i] > t[i]) return 1;
if(t[i] > s[i]) return 0;
}
return 1;
}
vector<int> mult(vector<int> s, vector<int> t) {
vector<int> ans((int) s.size()+(int) t.size(),0);
if(s == vector<int>{0} or t == vector<int>{0}) return vector<int>{0};
for(int i = 0; i < s.size(); i++) {
for(int j = 0; j < t.size(); j++) {
ans[i+j]+= s[i]*t[j];
}
}
for(int i = 0; i < ans.size(); i++) {
if(ans[i] >= base) {
if(i+1 == (int) ans.size()) ans.pb(0);
ans[i+1]+= ans[i]/base;
ans[i]%= base;
}
}
while(ans.size() > 1 && ans.back() == 0) ans.pop_back();
return ans;
}
vector<int> add(vector<int> s, vector<int> t) {
vector<int> ans = s;
for(int i = 0; i < t.size(); i++) {
if(i == (int) ans.size()) ans.pb(0);
ans[i]+= t[i];
}
for(int i = 0; i < ans.size(); i++) {
if(ans[i] >= base) {
if(i+1 == (int) ans.size()) ans.pb(0);
ans[i+1]+= ans[i]/base;
ans[i]%= base;
}
}
while(ans.size() > 1 && ans.back() == 0) ans.pop_back();
return ans;
}
vector<int> addref(vector<int> &s, vector<int> &t) {
vector<int> ans = s;
for(int i = 0; i < t.size(); i++) {
if(i == (int) ans.size()) ans.pb(0);
ans[i]+= t[i];
}
for(int i = 0; i < ans.size(); i++) {
if(ans[i] >= base) {
if(i+1 == (int) ans.size()) ans.pb(0);
ans[i+1]+= ans[i]/base;
ans[i]%= base;
}
}
while(ans.size() > 1 && ans.back() == 0) ans.pop_back();
return ans;
}
vector<int> trans(int x) {
if(x == 0) return vector<int>{0};
vector<int> ans;
while(x != 0) {
ans.pb(x%base);
x/= base;
}
return ans;
}
int transback(vector<int> s) {
int ans = 0;
int p10 = 1;
for(int i = 0; i < s.size(); i++) {
ans+= p10*s[i];
p10*= base;
}
return ans;
}
vector<int> dp[260][10*64+10];
void precomp() {
// dp(i,sum) = # de (q_0,q_1,...,q_i) tal que a soma é no maximo sum
for(int i = 0; i < R; i++) {
for(int j = 0; j <= k; j++) {
dp[i][j] = vector<int>{0};
}
}
for(int j = 0; j <= k; j++) {
dp[0][j] = trans(j+1);
}
for(int i = 1; i < R; i++) {
dp[i][0] = trans(1);
for(int j = 1; j <= k; j++) {
dp[i][j] = addref(dp[i][j-1],dp[i-1][j]);
}
}
}
vector<int> querysmaller(vector<int> q) {
vector<int> ans = {0};
int sumq = 0;
for(int i = R-1; i >= 0; i--) {
for(int j = 0; j <= q[i]-1 && k-j-sumq >= 0; j++) {
if(i == 0) ans = add(ans,trans((int)1));
else ans = add(ans,dp[i-1][k-j-sumq]);
}
sumq+= q[i];
}
if(sumq <= k) ans = add(ans,trans(1));
return ans;
}
vector<int> findg(vector<int> g) {
vector<int> ans(R,0);
int sumans = 0;
vector<int> cur = {1};
for(int i = R-1; i >= 0; i--) {
ans[i] = 0;
for(int j = 1; j <= k-sumans; j++) {
vector<int> newcur;
if(i == 0) newcur = add(cur,trans(1));
else newcur = add(cur,dp[i-1][k-sumans-j+1]);
if(!geq(g,newcur)) break;
cur = newcur;
ans[i] = j;
}
sumans+= ans[i];
}
return ans;
}
void encode(int32_t n, int32_t m[])
{
k = 5*n;
R = 220;
// clock_t tStart = clock();
precomp();
// printf("Time taken to precomp: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
vector<int> vm = trans(0);
vector<int> p256 = trans(1);
for(int i = 0; i < n; i++) {
vm = add(vm,mult(p256,trans(m[i])));
p256 = mult(p256,trans(256));
}
vector<int> ans = findg(add(vm,trans(1)));
for(int i = 0; i < ans.size(); i++) {
for(int j = 0; j < ans[i]; j++) {
send((int32_t) i);
}
}
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fr first
#define sc second
#define int long long
// const int maxn = 1e5+10;
// const int inf = 1e18+10;
static int R1;
static int k1;
static int base1 = 1e8;
bool geq1(vector<int> s, vector<int> t) {
if(s.size() > t.size()) return 1;
if(t.size() > s.size()) return 0;
for(int i = (int) s.size() -1; i >= 0; i--) {
if(s[i] > t[i]) return 1;
if(t[i] > s[i]) return 0;
}
return 1;
}
vector<int> mult1(vector<int> s, vector<int> t) {
vector<int> ans((int) s.size()+(int) t.size(),0);
if(s == vector<int>{0} or t == vector<int>{0}) return vector<int>{0};
for(int i = 0; i < s.size(); i++) {
for(int j = 0; j < t.size(); j++) {
ans[i+j]+= s[i]*t[j];
}
}
for(int i = 0; i < ans.size(); i++) {
if(ans[i] >= base1) {
if(i+1 == (int) ans.size()) ans.pb(0);
ans[i+1]+= ans[i]/base1;
ans[i]%= base1;
}
}
while(ans.size() > 1 && ans.back() == 0) ans.pop_back();
return ans;
}
vector<int> neg(vector<int> s) {
for(int i = 0; i < s.size(); i++) {
s[i]*= -1;
}
return s;
}
vector<int> add1(vector<int> s, vector<int> t) {
vector<int> ans = s;
for(int i = 0; i < t.size(); i++) {
if(i == (int) ans.size()) ans.pb(0);
ans[i]+= t[i];
}
for(int i = 0; i < ans.size(); i++) {
if(ans[i] < 0) {
if(i+1 == (int) ans.size()) ans.pb(0);
int qt = (ans[i]-1)/base1 + 1;
ans[i]+= qt*base1;
ans[i+1]-= qt;
}
if(ans[i] >= base1) {
if(i+1 == (int) ans.size()) ans.pb(0);
ans[i+1]+= ans[i]/base1;
ans[i]%= base1;
}
}
while(ans.size() > 1 && ans.back() == 0) ans.pop_back();
return ans;
}
vector<int> add1ref(vector<int> &s, vector<int> &t) {
vector<int> ans = s;
for(int i = 0; i < t.size(); i++) {
if(i == (int) ans.size()) ans.pb(0);
ans[i]+= t[i];
}
for(int i = 0; i < ans.size(); i++) {
if(ans[i] < 0) {
if(i+1 == (int) ans.size()) ans.pb(0);
int qt = (ans[i]-1)/base1 + 1;
ans[i]+= qt*base1;
ans[i+1]-= qt;
}
if(ans[i] >= base1) {
if(i+1 == (int) ans.size()) ans.pb(0);
ans[i+1]+= ans[i]/base1;
ans[i]%= base1;
}
}
while(ans.size() > 1 && ans.back() == 0) ans.pop_back();
return ans;
}
vector<int> trans1(int x) {
if(x == 0) return vector<int>{0};
vector<int> ans;
while(x != 0) {
ans.pb(x%base1);
x/= base1;
}
return ans;
}
int trans1back1(vector<int> s) {
int ans = 0;
int p10 = 1;
for(int i = 0; i < s.size(); i++) {
ans+= p10*s[i];
p10*= base1;
}
return ans;
}
vector<int> dp1[260][10*64+10];
void precomp1() {
// dp(i,sum) = # de (q_0,q_1,...,q_i) tal que a soma é no maximo sum
for(int i = 0; i < R1; i++) {
for(int j = 0; j <= k1; j++) {
dp1[i][j] = vector<int>{0};
}
}
for(int j = 0; j <= k1; j++) {
dp1[0][j] = trans1(j+1);
}
for(int i = 1; i < R1; i++) {
dp1[i][0] = trans1(1);
for(int j = 1; j <= k1; j++) {
dp1[i][j] = add1ref(dp1[i][j-1],dp1[i-1][j]);
// dp1[i][j] = add1(dp1[i][j],dp1[i][j-1]);
// dp1[i][j] = add1(dp1[i][j],dp1[i-1][j]);
}
}
}
vector<int> querysmaller1(vector<int> q) {
vector<int> ans = {0};
int sumq = 0;
for(int i = R1-1; i >= 0; i--) {
for(int j = 0; j <= q[i]-1 && k1-j-sumq >= 0; j++) {
if(i == 0) ans = add1(ans,trans1((int)1));
else ans = add1(ans,dp1[i-1][k1-j-sumq]);
}
sumq+= q[i];
}
if(sumq <= k1) ans = add1(ans,trans1(1));
return ans;
}
vector<int> findg1(vector<int> g) {
vector<int> ans(R1,0);
int sumans = 0;
for(int i = R1-1; i >= 0; i--) {
ans[i] = 0;
for(int j = 1; j+sumans <= k1; j++) {
ans[i] = j;
if(!(geq1(g,querysmaller1(ans)))) {
ans[i] = j-1;
break;
}
}
sumans+= ans[i];
}
return ans;
}
void decode(int32_t n, int32_t L, int32_t X[])
{
k1 = 5*n;
R1 = 220;
// clock_t tStart = clock();
precomp1();
// printf("Time taken to precomp1: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
vector<int> q(R1,0);
for(int i = 0; i < L; i++) {
q[X[i]]++;
}
vector<int> vm = add1(querysmaller1(q),neg(trans1(1)));
vector<int> m(n);
vector<vector<int>> ps;
ps.pb(trans1(1));
for(int i = 1; i <= n-1; i++) {
ps.pb(mult1(ps.back(),trans1(256)));
}
for(int i = n-1; i >= 0; i--) {
m[i] = 0;
while(geq1(vm,ps[i])) {
m[i]++;
vm = add1(vm,neg(ps[i]));
}
}
for(int i =0; i < n; i++) {
output((int32_t) m[i]);
}
}
Compilation message
encoder.cpp: In function 'std::vector<long long int> mult(std::vector<long long int>, std::vector<long long int>)':
encoder.cpp:31:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
encoder.cpp:32:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int j = 0; j < t.size(); j++) {
| ~~^~~~~~~~~~
encoder.cpp:37:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
encoder.cpp: In function 'std::vector<long long int> add(std::vector<long long int>, std::vector<long long int>)':
encoder.cpp:51:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i = 0; i < t.size(); i++) {
| ~~^~~~~~~~~~
encoder.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
encoder.cpp: In function 'std::vector<long long int> addref(std::vector<long long int>&, std::vector<long long int>&)':
encoder.cpp:70:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i = 0; i < t.size(); i++) {
| ~~^~~~~~~~~~
encoder.cpp:75:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
encoder.cpp: In function 'long long int transback(std::vector<long long int>)':
encoder.cpp:99:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
encoder.cpp: In function 'void encode(int32_t, int32_t*)':
encoder.cpp:181:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | for(int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
decoder.cpp: In function 'std::vector<long long int> mult1(std::vector<long long int>, std::vector<long long int>)':
decoder.cpp:30:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
decoder.cpp:31:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int j = 0; j < t.size(); j++) {
| ~~^~~~~~~~~~
decoder.cpp:36:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
decoder.cpp: In function 'std::vector<long long int> neg(std::vector<long long int>)':
decoder.cpp:48:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
decoder.cpp: In function 'std::vector<long long int> add1(std::vector<long long int>, std::vector<long long int>)':
decoder.cpp:57:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i = 0; i < t.size(); i++) {
| ~~^~~~~~~~~~
decoder.cpp:62:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
decoder.cpp: In function 'std::vector<long long int> add1ref(std::vector<long long int>&, std::vector<long long int>&)':
decoder.cpp:83:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int i = 0; i < t.size(); i++) {
| ~~^~~~~~~~~~
decoder.cpp:88:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
decoder.cpp: In function 'long long int trans1back1(std::vector<long long int>)':
decoder.cpp:120:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
11556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
11464 KB |
Output is correct |
| 2 |
Correct |
112 ms |
12144 KB |
Output is correct |
| 3 |
Correct |
172 ms |
13180 KB |
Output is correct |
| 4 |
Correct |
205 ms |
13300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
11644 KB |
Output is correct |
| 2 |
Correct |
109 ms |
12320 KB |
Output is correct |
| 3 |
Correct |
175 ms |
13168 KB |
Output is correct |
| 4 |
Correct |
195 ms |
13140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
11456 KB |
Output is correct |
| 2 |
Correct |
200 ms |
13000 KB |
Output is correct |
| 3 |
Correct |
285 ms |
14192 KB |
Output is correct |
| 4 |
Correct |
472 ms |
16076 KB |
Output is correct |
| 5 |
Correct |
496 ms |
16772 KB |
Output is correct |
| 6 |
Correct |
519 ms |
16732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
198 ms |
13196 KB |
Output is correct - P = 5.000000 |
| 2 |
Correct |
510 ms |
16796 KB |
Output is correct - P = 5.000000 |
| 3 |
Correct |
550 ms |
17016 KB |
Output is correct - P = 5.000000 |
| 4 |
Correct |
973 ms |
20756 KB |
Output is correct - P = 5.000000 |
| 5 |
Correct |
1135 ms |
23328 KB |
Output is correct - P = 5.000000 |
| 6 |
Correct |
1264 ms |
24308 KB |
Output is correct - P = 5.000000 |
| 7 |
Correct |
1254 ms |
24316 KB |
Output is correct - P = 5.000000 |
