oj.uz

답안 #533340

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
533340 2022-03-05T14:09:46 Z jeffshlez 사탕 분배 (IOI21_candies) C++17
0 / 100
 244 ms 14232 KB 
#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++)
      |                   ~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 244 ms 14232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 260 KB Output isn't correct
2 Halted 0 ms 0 KB -