#pragma warning(disable:4996)
using namespace std;
#include "candies.h"
#include <iostream>
#include <cassert>
#include <cstdio>
#include <vector>
// BEGIN SECRET
#include <string>
// END SECRET
int getRangeFromIndex(int start, int level, int level_n) {
start -= start % level;
start /= level;
return 2 * level_n - 2 * level_n / level + start;
}
// functino to convert any range to the minimal sum
// of ranges l*2^k to (l+1)*2^k - 1
// for instance, the range 15-22 will be split to
// 15-15 (15*2^0 - 16*2^0-1),
// 16-19 (4*2^2 - 5*2^2-1),
// 20-21 (10*2^1 - 11*2^1-1),
// 22-22 (22*2^0 - 23*2^0-1)
// the ranges are returned as an array that contains the indexes
// of the ranges, which is ordered like this:
// [2^k ranges of len 2^0][2^(k-1) ranges of len 2^1][2^(k-2) ranges of len 2^2]...[2^0 ranges of len 2^k]
// where 2^k=the size of the array (rounded up to the nearest power of 2)
// l - left bound of the range
// r - right bound of the range
// level_n - min power of 2 above n (2^k)
vector <int> find_ranges(int l, int r, int level_n) {
vector <int> ranges(0);
int level = 1;
while (l + level - 1 < r) {
if (l % level > 0) {
level /= 2;
ranges.push_back(getRangeFromIndex (l, level, level_n));
l += level;
level *= 2;
}
level *= 2;
}
while (l <= r) {
while (l + level - 1 > r)
level /= 2;
ranges.push_back(getRangeFromIndex(l, level, level_n));
l += level;
level /= 2;
}
return ranges;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int level = 1;
int n = size(c);
while (level < n)
level *= 2;
vector <int> adding(level*2);
fill(adding.begin(), adding.begin() + level, 0);
int q = size(v);
for (int j = 0; j < q; j++) {
vector <int> ranges = find_ranges(l[j], r[j], level);
for (int k = 0; k < size(ranges); k++)
adding[ranges[k]] += v[j];
}
vector <int> results(n);
fill(results.begin(), results.end(), 0);
for (int i = 0; i < n; i++) {
int crnt = 1;
while (crnt < level) {
results[i] += adding[getRangeFromIndex(i, crnt, level)];
if (results[i] > c[i]) {
results[i] = c[i];
break;
}
crnt *= 2;
}
}
return results;
}
Compilation message
candies.cpp:1: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
1 | #pragma warning(disable:4996)
|
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int k = 0; k < size(ranges); k++)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
244 ms |
14232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
