Submission #874212

# Submission time Handle Problem Language Result Execution time Memory
874212 2023-11-16T12:54:40 Z 12345678 Parrots (IOI11_parrots) C++17
100 / 100
1016 ms 92288 KB
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3", "unroll-loops")
using namespace std;

const int nx=65, 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;}
};

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=65, 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;}
};

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;
    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 186 ms 91712 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 225 ms 91988 KB Output is correct
2 Correct 227 ms 92084 KB Output is correct
3 Correct 251 ms 91764 KB Output is correct
4 Correct 259 ms 91908 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 225 ms 92012 KB Output is correct
2 Correct 224 ms 91968 KB Output is correct
3 Correct 255 ms 91888 KB Output is correct
4 Correct 265 ms 91780 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 210 ms 91908 KB Output is correct
2 Correct 276 ms 92080 KB Output is correct
3 Correct 282 ms 91716 KB Output is correct
4 Correct 385 ms 92164 KB Output is correct
5 Correct 378 ms 91992 KB Output is correct
6 Correct 410 ms 91996 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 258 ms 91952 KB Output is correct - P = 1.750000
2 Correct 395 ms 91948 KB Output is correct - P = 2.437500
3 Correct 405 ms 92040 KB Output is correct - P = 2.484848
4 Correct 683 ms 91968 KB Output is correct - P = 3.280000
5 Correct 881 ms 92288 KB Output is correct - P = 3.833333
6 Correct 933 ms 91924 KB Output is correct - P = 4.015873
7 Correct 1016 ms 92064 KB Output is correct - P = 4.078125