oj.uz

답안 #838143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
838143 2023-08-26T09:33:24 Z caganyanmaz 식물 비교 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -