# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
874204 |
2023-11-16T12:46:19 Z |
12345678 |
Parrots (IOI11_parrots) |
C++17 |
|
2000 ms |
145596 KB |
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3", "unroll-loops")
using namespace std;
const int nx=70, kx=256;
struct bignum
{
vector<int> val;
bignum(): val(nx, 0){}
bignum(int x)
{
val.assign(nx, 0);
for (int i=0; i<nx&&x>0; i++)
{
val[i]=x%kx;
x/=kx;
}
}
bignum &operator+=(const bignum &rhs)
{
int carry=0;
for (int i=0; i<nx; i++)
{
val[i]+=rhs.val[i]+carry;
carry=val[i]/kx;
val[i]-=carry*kx;
}
return *this;
}
bignum &operator-=(const bignum &rhs)
{
int carry=0;
for (int i=0; i<nx; i++)
{
val[i]-=rhs.val[i]+carry;
carry=0;
if (val[i]<0) {
val[i]+=kx;
carry++;
}
}
return *this;
}
friend bignum operator+(const bignum &lhs, const bignum &rhs) {return bignum(lhs)+=rhs;}
friend bignum operator-(const bignum &lhs, const bignum &rhs) {return bignum(lhs)+=rhs;}
int cmp(const bignum &rhs) {
for (int i=nx-1; i>=0; i--)
{
if (val[i]<rhs.val[i]) return -1;
if (val[i]>rhs.val[i]) return 1;
}
return 0;
}
bool operator<(const bignum &rhs) {return cmp(rhs)==-1;}
bool operator>(const bignum &rhs) {return cmp(rhs)==1;}
bool operator<=(const bignum &rhs) {return cmp(rhs)!=1;}
bool operator>=(const bignum &rhs) {return cmp(rhs)!=-1;}
bool operator==(const bignum &rhs) {return cmp(rhs)==0;}
bool operator!=(const bignum &rhs) {return cmp(rhs)!=0;}
string to_str()
{
auto res=val;
while (res.size()>1&&res.back()==0) res.pop_back();
reverse(res.begin(), res.end());
string s="";
for (auto x:res) s+=to_string(x)+" ";
s.pop_back();
return s;
}
};
vector<vector<bignum>> dp(580, vector<bignum> (270));
bool ok;
void encode(int N, int M[])
{
bignum vl, tmp;
if (!ok)
{
ok=1;
for (int i=0; i<580; i++)
{
for (int j=0; j<=min(i, 269); j++)
{
if (j==0||j==i) dp[i][j]=1;
else dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
}
}
}
for (int i=0; i<N; i++) vl.val[i]=M[N-1-i];
vector<int> s(kx+1);
int left=320;
for (int i=0; i<kx; i++)
{
tmp=0;
for (int j=left; j>=0; j--)
{
if (dp[kx-i-1+left-j][kx-i-1]+tmp>vl)
{
vl-=tmp;
s[i]=j;
left-=j;
break;
}
tmp+=dp[kx-i-1+left-j][kx-i-1];
}
}
s[kx]=left;
for (int i=0; i<kx; i++) for (int j=0; j<s[i+1]; j++) send(i);
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3", "unroll-loops")
using namespace std;
const int nx=70, kx=256;
struct bignum
{
vector<int> val;
bignum(): val(nx, 0){}
bignum(int x)
{
val.assign(nx, 0);
for (int i=0; i<nx&&x>0; i++)
{
val[i]=x%kx;
x/=kx;
}
}
bignum &operator+=(const bignum &rhs)
{
int carry=0;
for (int i=0; i<nx; i++)
{
val[i]+=rhs.val[i]+carry;
carry=val[i]/kx;
val[i]-=carry*kx;
}
return *this;
}
bignum &operator-=(const bignum &rhs)
{
int carry=0;
for (int i=0; i<nx; i++)
{
val[i]-=rhs.val[i]+carry;
carry=0;
if (val[i]<0) {
val[i]+=kx;
carry++;
}
}
return *this;
}
friend bignum operator+(const bignum &lhs, const bignum &rhs) {return bignum(lhs)+=rhs;}
friend bignum operator-(const bignum &lhs, const bignum &rhs) {return bignum(lhs)+=rhs;}
int cmp(const bignum &rhs) {
for (int i=nx-1; i>=0; i--)
{
if (val[i]<rhs.val[i]) return -1;
if (val[i]>rhs.val[i]) return 1;
}
return 0;
}
bool operator<(const bignum &rhs) {return cmp(rhs)==-1;}
bool operator>(const bignum &rhs) {return cmp(rhs)==1;}
bool operator<=(const bignum &rhs) {return cmp(rhs)!=1;}
bool operator>=(const bignum &rhs) {return cmp(rhs)!=-1;}
bool operator==(const bignum &rhs) {return cmp(rhs)==0;}
bool operator!=(const bignum &rhs) {return cmp(rhs)!=0;}
string to_str()
{
auto res=val;
while (res.size()>1&&res.back()==0) res.pop_back();
reverse(res.begin(), res.end());
string s="";
for (auto x:res) s+=to_string(x)+" ";
s.pop_back();
return s;
}
};
vector<vector<bignum>> dp(580, vector<bignum> (270));
bool ok2;
void decode(int N, int L, int X[])
{
bignum res=0;
if (!ok2)
{
ok2=1;
for (int i=0; i<580; i++)
{
for (int j=0; j<=min(i, 269); j++)
{
if (j==0||j==i) dp[i][j]=1;
else dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
}
}
}
int sm=0;
vector<int> s(kx+1, 0);
for (int i=0; i<L; i++) s[X[i]+1]++, sm++;
s[0]=320-sm;
vector<vector<bignum>> dp(580, vector<bignum> (270));
for (int i=0; i<580; i++)
{
for (int j=0; j<=min(i, 269); j++)
{
if (j==0||j==i) dp[i][j]=1;
else dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
}
}
int left=320;
for (int i=0; i<=kx; i++)
{
for (int j=left; j>s[i]; j--)
{
res+=dp[kx-i-1+left-j][kx-i-1];
}
left-=s[i];
}
//res+=s[kx];
vector<int> ans(N, 0);
for (int i=0; i<N; i++) ans[N-1-i]=res.val[i];
for (int i=0; i<N; i++) output(ans[i]);
}
/*
10
1 1 2 1 2 3 1 7 10 9
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
483 ms |
144624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1681 ms |
144964 KB |
Output is correct |
2 |
Correct |
1689 ms |
144972 KB |
Output is correct |
3 |
Correct |
1714 ms |
144828 KB |
Output is correct |
4 |
Correct |
1713 ms |
144868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1657 ms |
145292 KB |
Output is correct |
2 |
Correct |
1670 ms |
145224 KB |
Output is correct |
3 |
Correct |
1710 ms |
144988 KB |
Output is correct |
4 |
Correct |
1717 ms |
145120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1670 ms |
144964 KB |
Output is correct |
2 |
Correct |
1714 ms |
144940 KB |
Output is correct |
3 |
Correct |
1763 ms |
145488 KB |
Output is correct |
4 |
Correct |
1863 ms |
145484 KB |
Output is correct |
5 |
Correct |
1886 ms |
145384 KB |
Output is correct |
6 |
Correct |
1904 ms |
145056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1728 ms |
144860 KB |
Output is correct - P = 1.750000 |
2 |
Correct |
1906 ms |
145348 KB |
Output is correct - P = 2.437500 |
3 |
Correct |
1908 ms |
145204 KB |
Output is correct - P = 2.484848 |
4 |
Execution timed out |
2080 ms |
145172 KB |
Time limit exceeded |
5 |
Execution timed out |
2083 ms |
145448 KB |
Time limit exceeded |
6 |
Execution timed out |
2074 ms |
145580 KB |
Time limit exceeded |
7 |
Execution timed out |
2066 ms |
145596 KB |
Time limit exceeded |