Submission #598653

#	Time	Username	Problem	Language	Result	Execution time	Memory
598653		CaroLinda	Weirdtree (RMI21_weirdtree)	C++14	13 / 100	18 ms	6000 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>

//solving for k == 1

#define ll long long

const int MAXN = 1010;

using namespace std;

int N, Q;
int arr[MAXN];

void initialise(int n, int q, int h[]) {
	N = n;
	Q = q;

	for(int i = 1; i <= N; i++)
		arr[i] = h[i];
}
void cut(int l, int r, int k) {

	bool yes = false;

	meuLabel:

	vector<pair<int,int> > vec;

	for(int i = l ; i <= r; i++){
		vec.push_back(make_pair(arr[i],-i));
	}

	sort(vec.begin(), vec.end());	

	if(yes){
		for(int i = vec.size()-1; i >= 0 && k; i--, k-- )
			if(arr[-vec[i].second])
				arr[-vec[i].second]--;
		return;
	}

	ll s = 0;
	int qtd = 0;

	for(int i = vec.size()-1; i >= 0; i--){
		qtd++;
		s += vec[i].first;

		ll ant = (i == 0) ? 0 : vec[i-1].first;

		if(s-ant * qtd < k)
			continue;

		ll x = (s-k+qtd-1)/(ll)qtd;

		for(int j = i; j < vec.size(); j++){
			int id = -vec[j].second;
			k -= arr[id]-x;
			arr[id] = x;
		}


		if(x == 0 || k == 0)
			return;

		yes = true;
		goto meuLabel;

		return;
	}

	for(int i = l ; i <= r; i++)
		arr[i] = 0;
}
void magic(int i, int x) {
	arr[i] = x;
}
long long int inspect(int l, int r) {
	ll s = 0;
	for(int i = l; i <= r; i++)
		s += arr[i];
	return s;
}

Compilation message (stderr)

weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int j = i; j < vec.size(); j++){
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 8
• Subtask 3: 8 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 10
• Subtask 6: 0 / 21
• Subtask 7: 0 / 29