oj.uz

Submission #1058981

# Submission time Handle Problem Language Result Execution time Memory
1058981 2024-08-14T15:36:30 Z Lalic Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 18072 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4952 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 2 ms 4952 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 29 ms 8900 KB Output is correct
7 Correct 409 ms 10680 KB Output is correct
8 Correct 130 ms 17728 KB Output is correct
9 Correct 800 ms 18000 KB Output is correct
10 Execution timed out 4010 ms 18072 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4968 KB Output is correct
5 Execution timed out 4094 ms 4956 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4968 KB Output is correct
5 Execution timed out 4094 ms 4956 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Execution timed out 4090 ms 9160 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4968 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 5 ms 5212 KB Output is correct
7 Execution timed out 4097 ms 5852 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Execution timed out 4090 ms 5724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4952 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 2 ms 4952 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 29 ms 8900 KB Output is correct
7 Correct 409 ms 10680 KB Output is correct
8 Correct 130 ms 17728 KB Output is correct
9 Correct 800 ms 18000 KB Output is correct
10 Execution timed out 4010 ms 18072 KB Time limit exceeded
11 Halted 0 ms 0 KB -