Submission #1058981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058981		Lalic	Comparing Plants (IOI20_plants)	C++17	0 / 100	4097 ms	18072 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int MAXN = 2e5+10;

int N;
vector<int> adj[MAXN];

bool dfs(int ver, int ob){
	//~ cout << ver << "\n";
	if(ver==ob) return 1;
	
	for(auto u : adj[ver])
		if(dfs(u, ob)) return 1;
	
	return 0;
}

void init(int k, vector<int> r) {
	N=(int)r.size();
	for(int i=0;i<N;i++) adj[i].clear();
	
	while(1){
		vector<int> zero;
		for(int i=0;i<N;i++)
			if(!r[i]) zero.pb(i);
		
		if(zero.empty()) break;
		
		vector<int> proc;
		if((int)zero.size()==1 || zero[0]-zero[(int)zero.size()-1]+N>=k) proc.pb(zero[0]);
		
		for(int i=1;i<(int)zero.size();i++)
			if(zero[i]-zero[i-1]>=k) proc.pb(zero[i]);
			
		for(auto u : proc){
			for(int i=u;i>=u-k+1;i--)
				r[(i+N)%N]--;
		}
		
		for(auto u : proc){
			for(int i=u-k+1;i<=u+k-1;i++)
				if(r[(i+N)%N]>=0) adj[u].pb((i+N)%N);
		}
	}
}

int compare_plants(int x, int y) {
	int res1=dfs(x, y), res2=dfs(y, x);
	if((res1 && res2) || (!res1 && !res2)) return 0;
	if(res1) return 1;
	return -1;
}

//~ int main(){
	//~ int n=8, k=2;
	//~ vector<int> perm(n);
	//~ iota(all(perm), 1);
	
	//~ srand(2);
	//~ while(1){
		//~ cout << "searching..\n";
		//~ random_shuffle(all(perm));
		
		//~ vector<int> r(n);
		//~ for(int i=0;i<n;i++)
			//~ r[i]=(perm[(i+1)%n]>perm[i] ? 1 : 0);
		
		//~ for(int i=0;i<n;i++) cout << r[i] << " \n"[i==n-1];
			
		//~ vector<vector<int>> pos;
		//~ vector<int> aux(n);
		//~ iota(all(aux), 1);
		
		//~ do{
			//~ bool foi=1;
			
			//~ for(int i=0;i<n;i++){
				//~ int curr=(aux[(i+1)%n]>aux[i] ? 1 : 0);
				//~ if(r[i]!=curr){
					//~ foi=0;
					//~ break;
				//~ }
			//~ }
			
			//~ if(foi) pos.pb(aux);
		//~ }while(next_permutation(all(aux)));
		
		//~ init(k, r);
		
		//~ bool ok=1;
		//~ int q=10;
		//~ for(int i=0;i<q;i++){
			//~ int x=rand()%n, y=rand()%n;
			//~ if(x==y) continue;
			//~ if(x>y) swap(x, y);
			
			//~ cout << "x = " << x << " y = " << y << "\n";
			
			//~ bool acima=0, abaixo=0;
			//~ for(auto u : pos){
				//~ if(u[x]>u[y]) acima=1;
				//~ else abaixo=1;
			//~ }
			
			//~ int res;
			//~ if(acima && abaixo) res=0;
			//~ else if(acima) res=1;
			//~ else res=-1;
			
			//~ if(res!=compare_plants(x, y)){
				//~ cout << "found error at:\n";
				//~ cout << n << " " << k << "\n";
				//~ for(int j=0;j<n;j++) cout << r[j] << " \n"[j==n-1];
				//~ cout << "query for: " << x << " " << y << "\n";
				//~ cout << "expected: " << res << "\tfound: " << compare_plants(x, y) << "\n\n";
				
				//~ cout << "all possible permutations:\n";
				//~ for(auto u : pos)
					//~ for(int j=0;j<n;j++)
						//~ cout << u[j] << " \n"[j==n-1];
				//~ ok=0;
				//~ break;
			//~ }
		//~ }
		
		//~ if(!ok) break;
	//~ }			
			
			
//~ }

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25