제출 #300873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
300873		gs14004	식물 비교 (IOI20_plants)	C++17	11 / 100	79 ms	3448 KiB

plants

#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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25