oj.uz

Submission #838143

# Submission time Handle Problem Language Result Execution time Memory
838143 2023-08-26T09:33:24 Z caganyanmaz Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 5216 KB 
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int MXN = 2e5 + 5;
int k, n;

int fw[MXN];
void update(int i, int val) { for (i++;i<MXN;i+=i&(-i)) fw[i] += val; }
int get(int i) { int res = 0; for (;i>0;i-=i&(-i)) res += fw[i]; return res; }
int get(int l, int r) { return get(r) - get(l); }

int v[MXN];
int succ[MXN];
void init(int _k, vector<int> r) 
{
	debug(r);
	n = r.size();
	k = _k;
	assert(k * 2 > n);
	fill(succ, succ + n, -1);
	for (int i = 1; i <= n; i++)
	{
		int prev = -1;
		int current = -1;
		int first = MXN;
		for (int j = 0; j < n; j++)
		{
			if (v[j] != 0)
				continue;
			int ll = j+1;
			int rr = j+k;
			int pc = 0;
			if (j == 1)
				debug(ll, rr);
			if (rr > n)
				pc = get(ll, n) + get(0, rr-n);
			else
				pc = get(ll, rr);
			debug(i, j, pc, pc + r[j], prev);
			if (pc + r[j] < k-1)
				continue;
			first = min(first, j);
			if (prev != -1 && j - prev >= k)
				current = j;
			prev = j;

		}
		if (current == -1)
			current = first;
		debug(current);
		v[current] = i;
		update(current, 1);
	}

}

int compare_plants(int x, int y) 
{
	if (v[x] > v[y])
		return 1;
	if (v[y] > v[x])
		return -1;
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 464 KB Output is correct
7 Correct 276 ms 5060 KB Output is correct
8 Correct 2 ms 444 KB Output is correct
9 Correct 9 ms 468 KB Output is correct
10 Correct 273 ms 5064 KB Output is correct
11 Correct 173 ms 5044 KB Output is correct
12 Correct 191 ms 5216 KB Output is correct
13 Correct 243 ms 5068 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 464 KB Output is correct
7 Correct 276 ms 5060 KB Output is correct
8 Correct 2 ms 444 KB Output is correct
9 Correct 9 ms 468 KB Output is correct
10 Correct 273 ms 5064 KB Output is correct
11 Correct 173 ms 5044 KB Output is correct
12 Correct 191 ms 5216 KB Output is correct
13 Correct 243 ms 5068 KB Output is correct
14 Execution timed out 4043 ms 5212 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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