제출 #533343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533343		jeffshlez	Distributing Candies (IOI21_candies)	C++17	0 / 100	257 ms	9384 KiB

candies

#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) {
    if (true) {
	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;
    }
    else {
    vector <int> results (size(c));
    fill (results.begin(), results.end(), 0);
    for (int j = 0; j < size(v); j++) {
    	for (int k = l[j]; k <= r[j]; k++) {
        	results[k] += v[j];
            if (results[k] < 0)
            	results[k] = 0;
            if (results[k] > c[k])
            	results[k] = c[k];
        }
    }
    return results;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (int k = 0; k < size(ranges); k++)
      |                   ~~^~~~~~~~~~~~~~
candies.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int j = 0; j < size(v); j++) {
      |                     ~~^~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33