oj.uz

Submission #385218

# Submission time Handle Problem Language Result Execution time Memory
385218 2021-04-03T17:30:38 Z rqi Packing Biscuits (IOI20_biscuits) C++14
21 / 100
 15 ms 896 KB 
#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;

#define sz(x) (int)(x).size()
#define pb push_back

int k;
vl a;
ll x;

ll tpow[64];

bool possible(ll y){
	vl A = a;
	
	for(int i = 0; i <= 59; i++){
		if((y>>i)&1){
			A[i]-=x;
		}
		
		if(A[i] < 0) return 0;
		if(i+1 < 60){
			A[i+1]+=A[i]/2;
		}
	}
	//cout << y << "\n";
	return 1;
}

ll solveCase1(){
	while(sz(a) < 60){
		a.pb(0);
	}
	int ans = 0;
	for(int y = 0; y <= 100000; y++){
		if(possible(y)){
			ans++;
		}
	}
	return ans;
}

ll restr[62];
ll dp[62];

ll getDP(ll v, int bitnum){
	assert(v >= 0);
	if(bitnum == 0){
		if(v == 0){
			return 1;
		}
		else if(v == 1){
			return dp[bitnum];
		}
		assert(false);
	}

	if(v < tpow[bitnum]){
		return getDP(v, bitnum-1);
	}

	if(restr[bitnum] < tpow[bitnum]){
		return getDP(v-tpow[bitnum], bitnum-1);
	}

	return dp[bitnum-1]+getDP(min(v-tpow[bitnum], restr[bitnum]-tpow[bitnum]), bitnum-1);
}

ll count_tastiness(ll _x, vl _a) {
	x = _x;
	a = _a;
	while(sz(a) < 62){
		a.pb(0);
	}

	k = sz(a);

	tpow[0] = 1;
	for(int i = 1; i < 64; i++){
		tpow[i] = tpow[i-1]*2;
	}

	// bool CASE1 = 1;

	// if(CASE1){
	// 	return solveCase1();
	// }

	restr[0] = a[0];
	for(int i = 1; i <= 61; i++){
		restr[i] = restr[i-1]+tpow[i]*a[i];
	}

	for(int i = 0; i <= 61; i++){
		restr[i]/=x;
	}

	if(restr[0] >= 1){
		dp[0] = 2;
	}
	else{
		dp[0] = 1;
	}

	for(int i = 1; i <= 61; i++){
		dp[i] = getDP(tpow[i+1]-1, i);
	}

	//assert(solveCase1() == dp[59]);
	assert(dp[59] == dp[60] && dp[60] == dp[61]);
	return dp[59];
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 384 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Incorrect 1 ms 364 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 364 KB Output is correct
2 Incorrect 15 ms 896 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Incorrect 1 ms 364 KB Output isn't correct
34 Halted 0 ms 0 KB -