oj.uz

Submission #300873

# Submission time Handle Problem Language Result Execution time Memory
300873 2020-09-17T14:41:54 Z gs14004 Comparing Plants (IOI20_plants) C++17
11 / 100
 79 ms 3448 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define rank fuck
using namespace std;
using lint = long long;
using llf = long double;
using pi = pair<lint, lint>;
const int MAXN = 200005;
 
int adj[305][305];
int n, rank[MAXN];
 
int dist(int x, int y){
	int d = abs(y - x);
	return min(d, n - d);
}
 
void init(int k, std::vector<int> r) {
	n = sz(r);
	if(n > 300) return;
	int layer = 0;
	while(count(rank, rank + n, 0)){
		vector<int> vect;
		for(int j=0; j<n; j++){
			if(r[j] || rank[j]) continue;
			bool claim = true;
			for(int x=1; x<=k-1; x++){
				if(r[(j-x+n)%n] == 0) claim = false; 
			}
			if(claim) vect.push_back(j);
		}
		layer++;
		for(auto &j : vect) rank[j] = layer;
		for(auto &j : vect){
			r[j] = k - 1;
			for(int x=1; x<=k-1; x++){
				r[(j-x+n)%n]--;
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(rank[j] > rank[i] && dist(i, j) < k){
				adj[j][i] = 1;
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			for(int k=0; k<n; k++){
				adj[j][k] |= (adj[j][i] & adj[i][k]);
			}
		}
	}
	return;
}
 
int compare_plants(int x, int y) {
	if(n > 300) return 69;
	if(adj[x][y]) return -1;
	if(adj[y][x]) return 1;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 64 ms 3192 KB Output is correct
7 Incorrect 79 ms 3448 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 70 ms 3320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 39 ms 1272 KB Output is correct
8 Correct 41 ms 1272 KB Output is correct
9 Correct 42 ms 1272 KB Output is correct
10 Correct 42 ms 1272 KB Output is correct
11 Correct 40 ms 1272 KB Output is correct
12 Correct 41 ms 1276 KB Output is correct
13 Correct 42 ms 1400 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 64 ms 3192 KB Output is correct
7 Incorrect 79 ms 3448 KB Output isn't correct
8 Halted 0 ms 0 KB -