oj.uz

Submission #1063303

# Submission time Handle Problem Language Result Execution time Memory
1063303 2024-08-17T16:41:24 Z Itamar Comparing Plants (IOI20_plants) C++14
14 / 100
 4000 ms 32692 KB 
#include<vector>
#define vi vector<int>
using namespace std;
#include<queue>
#include <set>
const int siz = 2e5+2;
int ans[siz];
int N,K;
vi R;
int dis(int a, int b){ // oriented
	if(b > a)return b-a;
	return b-a+N;
}
queue<int> q;

struct node{
	int l,r,mid,minir,plus;
	node* sl,*sr;
	node(int li, int ri){
		l = li, r = ri, mid = (l+r)/2,plus=0;
		if(l<r){
			sl = new node(l,mid);
			sr = new node(mid+1,r);
			minir = min(sl->minir,sr->minir);
		}else{
			minir = R[l];
		}
	}
	void push(){
		if(l==r)return;
		sl->minir+=plus;
		sr->minir+=plus;
		sl->plus+=plus;
		sr->plus+=plus;
		plus=0;
	}
	void update(int a, int b, int p){
		push();
		if(r < a || l > b)return;
		if(a <= l && b >= r){
			minir+=p;
			plus+=p;
		}else{
			sl->update(a,b,p);
			sr->update(a,b,p);
			minir = min(sl->minir,sr->minir);
		}
	}
	int find(){
     	push();
		if(l==r){
			if(minir<=0){
				return l;
			}
			else return 1e9;
		}
		if(sl->minir<=0){
			
			return sl->find();
		}
		else if(sr->minir <=0)return sr->find();
		else return 1e9;
	}
};
set<int> s;
node* seg;
bool check(int i){
	for(auto j : s)if(dis(j,i)<K)return 0;
			q.push(i);
	return 1;
	auto it = s.find(i);
	if(it == s.end())return 0;
	auto it2 = it;
	int j;
	if(it2!=s.begin())j = *(--it2);
	else j =  *(s.rbegin());
	if(*it2 == i){
		q.push(i);
		return 1;
	}
	if(dis(*it2,i)>=K ){
		q.push(i);
		return 1;
	}
	else{
		return 0;
	}
}
void ins(int i){ // he now has r[i]=0
	//auto it = s.find(i);
	s.insert(i);
}
int mod(int i){
	return (i+N)%N;
}
void er(int i){ // i was considered as a maximum
	auto it = s.find(i);
	if(i>=K-1){
		seg->update(i-K+1,i,-1);
	}else{
		seg->update(0,i,-1);
		seg->update(mod(i-K+1),N-1,-1);
	}
	auto it1 = it, it2 = it;
	it2++;
	s.erase(i);
	if(it2 == s.end())it2 = s.begin();
	check(*it2);
}
void init(int k, std::vector<int> r) {
	if(N>200)return;
	N = r.size(), K = k, R = r;
	 seg = new node(0,N-1);
	
	while(true){
		int f = seg->find();
		seg->update(f,f,1e9);
		if(f==1e9)break;
		ins(f);
	}
	for(int i = 0; i < N; i++)if(r[i]==0){
		check(i);
	}
	int ito = 1;
	vi vis(N);
	while(ito<=N){

		//int i = q.front();
		int i=0;
		for(int j : s)if(check(j))i=j;
		//q.pop();
		if(vis[i])continue;
		if(check(i)==0)continue;
		vis[i]=1;
		er(i);
		ans[i]=ito;
		ito++;
		vi vec;
		while(true){
		int f = seg->find();
			seg->update(f,f,1e9);
		if(f==1e9)break;
		ins(f);
		}
	}
	/*for(int i = 0; i < N; i++){
		if(ans[i]==0){
			for(int j = 0; j < 2e9; j++){
				ans[i] = (ans[i]+1)%N;
			}
		}
	}*/
	int i =5;
	return;
}

int compare_plants(int x, int y) {
	if(ans[x]<ans[y])return 1;
	return -1;
}

Compilation message

plants.cpp: In function 'bool check(int)':
plants.cpp:74:6: warning: variable 'j' set but not used [-Wunused-but-set-variable]
   74 |  int j;
      |      ^
plants.cpp: In function 'void er(int)':
plants.cpp:104:7: warning: variable 'it1' set but not used [-Wunused-but-set-variable]
  104 |  auto it1 = it, it2 = it;
      |       ^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:153:6: warning: unused variable 'i' [-Wunused-variable]
  153 |  int i =5;
      |      ^

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 37 ms 5732 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 444 KB Output is correct
10 Correct 42 ms 5708 KB Output is correct
11 Correct 231 ms 5608 KB Output is correct
12 Correct 34 ms 5712 KB Output is correct
13 Correct 35 ms 5672 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 37 ms 5732 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 444 KB Output is correct
10 Correct 42 ms 5708 KB Output is correct
11 Correct 231 ms 5608 KB Output is correct
12 Correct 34 ms 5712 KB Output is correct
13 Correct 35 ms 5672 KB Output is correct
14 Correct 89 ms 7940 KB Output is correct
15 Correct 278 ms 31572 KB Output is correct
16 Correct 51 ms 7764 KB Output is correct
17 Correct 305 ms 31572 KB Output is correct
18 Execution timed out 4081 ms 32692 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 330 ms 5532 KB Output is correct
4 Execution timed out 4072 ms 29780 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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