oj.uz

Submission #533342

# Submission time Handle Problem Language Result Execution time Memory
533342 2022-03-05T14:13:26 Z jeffshlez Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 13204 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) {
    if (false) {
	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;
    }
}

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: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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 300 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5040 ms 7528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 187 ms 8084 KB Output is correct
3 Correct 166 ms 6008 KB Output is correct
4 Execution timed out 5012 ms 13204 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 433 ms 7644 KB Output is correct
4 Correct 452 ms 4004 KB Output is correct
5 Execution timed out 5058 ms 10840 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 300 KB Output is correct
6 Execution timed out 5040 ms 7528 KB Time limit exceeded
7 Halted 0 ms 0 KB -