| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 533339 | jeffshlez | 사탕 분배 (IOI21_candies) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
int main() {
// BEGIN SECRET
const std::string input_secret = "lrts0z0ktpqc670i0etyqgyb45dt1dysq5ap2mzg";
const std::string output_secret = "4lpv73iykswp9e3nppi3jw2qggm5dfz29yy9nzpq";
char secret[1000];
assert(1 == scanf("%s", secret));
if (std::string(secret) != input_secret) {
printf("%s\n", output_secret.c_str());
printf("PV\n");
printf("Possible tampering with the input\n");
fclose(stdout);
return 0;
}
// END SECRET
int n;
assert(1 == scanf("%d", &n));
std::vector<int> c(n);
for (int i = 0; i < n; ++i) {
assert(scanf("%d", &c[i]) == 1);
}
int q;
assert(1 == scanf("%d", &q));
std::vector<int> l(q), r(q), v(q);
for (int i = 0; i < q; ++i) {
assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
}
std::vector<int> ans = distribute_candies(c, l, r, v);
// BEGIN SECRET
printf("%s\n", output_secret.c_str());
if (int(ans.size()) != n) {
printf("WA\nReturned array is of the wrong size (len=%d).\n", (int)ans.size());
return 0;
}
printf("OK\n");
// END SECRET
for (int i = 0; i < n; ++i) {
if (i > 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
fclose(stdout);
return 0;
}