oj.uz

답안 #314637

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
314637 2020-10-20T13:58:16 Z kostia244 식물 비교 (IOI20_plants) C++17
14 / 100
 4000 ms 3576 KB 
#include "plants.h"
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const int maxn = 1<<17;
int n, k, ord[maxn], oh[maxn];
int in(int l, int r, int x) {
	if(l >= n) l%=n;
	if(r >= n) r%=n;
	if(l > r) {
		return in(l, n-1, x) || in(0, r, x);
	}
	return l <= x && x <= r;
}
void ah(int i, int x) {
	for(int j = 1; j < k; j++) oh[(i+j)%n]+=x;
}
void init(int K, std::vector<int> r) {
	k = K;
	n = r.size();
	if(k == 2) {
		int cur = 0;
		for(int j = 0, i = 0; i < n; i++) {
			while(r[j]) j = (j+1)%n;
			ord[i] = j;
			if(i == j) j++;
		}
		return;
	}
	for(int i = 0; i < n; i++) if(r[i] == 0) ah(i, 1);
	for(int L = n; L; L--) {
		int f = 1;
		for(int i = 0; f && i < n; i++) if(!oh[i] && r[i] == 0 && !ord[i]) {
			ord[i] = L;
			ah(i, -1);
			for(int j = 1; j < k; j++) {
				int pos = (n-j+i)%n;
				if(--r[pos] == 0) ah(pos, 1);
			}
			f = 0;
		}
	}
	return;
}

int compare_plants(int x, int y) {
	if(k == 2) {
		if(in(x, ord[x], y)) return -1;
		if(in(y, ord[y], x)) return 1;
		return 0;
	}
	return (ord[x] > ord[y]) - (ord[x] < ord[y]);
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:22:7: warning: unused variable 'cur' [-Wunused-variable]
   22 |   int cur = 0;
      |       ^~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 18 ms 384 KB Output is correct
7 Correct 463 ms 3384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 18 ms 384 KB Output is correct
10 Correct 459 ms 3332 KB Output is correct
11 Correct 317 ms 3192 KB Output is correct
12 Correct 324 ms 3576 KB Output is correct
13 Correct 554 ms 3452 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 18 ms 384 KB Output is correct
7 Correct 463 ms 3384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 18 ms 384 KB Output is correct
10 Correct 459 ms 3332 KB Output is correct
11 Correct 317 ms 3192 KB Output is correct
12 Correct 324 ms 3576 KB Output is correct
13 Correct 554 ms 3452 KB Output is correct
14 Execution timed out 4078 ms 2948 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -