| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 919958 | Lobo | 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 "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 vector<int> maxt1;
static int R1;
static int k1;
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] >= 10) {
if(i+1 == (int) ans.size()) ans.pb(0);
ans[i+1]+= ans[i]/10;
ans[i]%= 10;
}
}
while(ans.size() > 1 && ans.back() == 0) ans.pop_back();
if(geq1(ans,maxt1)) return maxt1;
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] >= 10) {
if(i+1 == (int) ans.size()) ans.pb(0);
ans[i+1]+= ans[i]/10;
ans[i]%= 10;
}
// if(ans[i] <= -10) {
// if(i+1 == (int) ans.size()) ans.pb(0);
// ans[i+1]+= ans[i]/10;
// ans[i]%= 10;
// }
}
for(int i = 0; i+1 < ans.size(); i++) {
while(ans[i] < 0) {
ans[i]+= 10;
ans[i+1]-= 1;
}
}
for(int i = 0; i < ans.size(); i++) {
if(ans[i] >= 10) {
if(i+1 == (int) ans.size()) ans.pb(0);
ans[i+1]+= ans[i]/10;
ans[i]%= 10;
}
}
while(ans.size() > 1 && ans.back() == 0) ans.pop_back();
if(geq1(ans,maxt1)) return maxt1;
return ans;
}
vector<int> trans1(int x) {
if(x == 0) return vector<int>{0};
vector<int> ans;
while(x != 0) {
ans.pb(x%10);
x/= 10;
}
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*= 10;
}
return ans;
}
vector<int> dp1[260][10*64+10];
void precomp1() {
maxt1.pb(1);
for(int i = 0; i <= 40; i++) {
maxt1.pb(0);
}
// 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++) {
for(int x = 0; x <= j; x++) {
dp1[i][j] = add1(dp1[i][j],dp1[i-1][j-x]);
}
}
}
}
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(int n, int L, int X[])
{
k1 = 5*n;
R1 = 60;
precomp1();
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);
for(int i = n-1; i >= 0; i--) {
vector<int> p256 = trans1(1);
for(int j = 0; j < i; j++) {
p256 = mult1(p256,trans1(256));
}
m[i] = 0;
while(geq1(vm,p256)) {
m[i]++;
vm = add1(vm,neg(p256));
}
}
for(int i =0; i < n; i++) {
output(m[i]);
}
}