oj.uz

Submission #305142

# Submission time Handle Problem Language Result Execution time Memory
305142 2020-09-22T15:53:21 Z junseo Packing Biscuits (IOI20_biscuits) C++17
0 / 100
 11 ms 896 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define rmin(r, x) r = min(r, x)
#define rmax(r, x) r = max(r, x)
#define ends ' '
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int maxk = 65;
const int maxa = 2e5 + 10;
 
bool p;
ll r[maxk], c[maxk];
 
ll get_r(ll T) {
	if(!T)		return 1;
	if(T == 1)	return 1 + p;
	int i = 63 - __builtin_clzll(T);
	return (r[i - 1] >= 0 ? c[i - 1] : 0) + get_r(T - (1LL << i));
}
 
long long count_tastiness(long long x, vector<ll> s) {
	int k = s.size();
	s.resize(maxk);
	for(int i = 1; i <= 60; ++i)	s[i] = s[i - 1] + (1LL << i) * s[i];
	
	p = (s[0] >= x);
	r[0] = p - 1;
	c[0] = p + 1;
 
	// cout << 0 << ends << r[0] << ends << c[0] << ends << (s[0] / x - 1) << endl;
	for(int i = 1; i <= 60; ++i) {
		ll T = s[i] / x - (1LL << i);
		if(T < 0) 		r[i] = -1;
		else {
			if((1LL << i) - 1 <= T)	r[i] = c[i - 1] - 1;
			else			r[i] = get_r(T) - 1;
		}
		c[i] = c[i - 1] + r[i] + 1;
		// cout << i << ends << r[i] << ends << c[i] << ends << T << endl;
	}
 
	return c[60];
}

Compilation message

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:30:6: warning: unused variable 'k' [-Wunused-variable]
   30 |  int k = s.size();
      |      ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 11 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 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -