oj.uz

Submission #598653

# Submission time Handle Problem Language Result Execution time Memory
598653 2022-07-18T16:05:34 Z CaroLinda Weirdtree (RMI21_weirdtree) C++14
13 / 100
 18 ms 6000 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 6 ms 368 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 6 ms 368 KB Output is correct
3 Runtime error 2 ms 1268 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 368 KB Output is correct
2 Correct 13 ms 396 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 368 KB Output is correct
2 Correct 13 ms 396 KB Output is correct
3 Runtime error 8 ms 6000 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 2900 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 6 ms 368 KB Output is correct
3 Runtime error 2 ms 1268 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 6 ms 368 KB Output is correct
3 Runtime error 2 ms 1268 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -