oj.uz

Submission #964538

# Submission time Handle Problem Language Result Execution time Memory
964538 2024-04-17T05:24:11 Z UmairAhmadMirza Robots (IOI13_robots) C++14
100 / 100
 1371 ms 28860 KB 
#include <bits/stdc++.h>
#include <robots.h>
using namespace std;
deque<pair<int,int>> toy,temp;
bool check(int A,int B,int T,int X[], int Y[],int lim){
	toy=temp;
	priority_queue<int> v;
	for (int i = 0; i < A; ++i)
	{
		while(toy.size()){
			if(toy[0].first>=X[i])
				break;
			v.push(toy[0].second);
			toy.pop_front();
		}
		int cnt=0;
		while(v.size() && cnt<lim){
			cnt++;
			v.pop();
		}
	}
	for(auto i:toy)
		v.push(i.second);
	toy.clear();
	stack<int> sz;
	while(v.size()){
		sz.push(v.top());
		v.pop();
	}
	int p=0;
	int cnt=0;
	int i=0;
	while(sz.size() && p<B){
		if(sz.top()>=Y[p]){
			p++;
			cnt=0;
		}
		else if(cnt==lim){
			p++;
			cnt=0;
		}
		else{
			cnt++;
			sz.pop();
		}
	}
	if(sz.size()==0)
		return 1;
	return 0;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
	int maxX=0,maxY=0;
	for (int i = 0; i < A; ++i)
		maxX=max(maxX,X[i]);
	for (int i = 0; i < B; ++i)
		maxY=max(maxY,Y[i]);
	for (int i = 0; i < T; ++i){
		if(W[i]>=maxX && S[i]>=maxY)
			return -1;
		temp.push_back({W[i],S[i]});
	}
	sort(temp.begin(), temp.end());
	sort(X,X+A);
	sort(Y,Y+B);
	int low=0,high=T;
	while(high-low>1){
		int mid=(low+high)/2;
		if(check(A,B,T,X,Y,mid))
			high=mid;
		else
			low=mid;
	}
	return high;
}

Compilation message

robots.cpp: In function 'bool check(int, int, int, int*, int*, int)':
robots.cpp:32:6: warning: unused variable 'i' [-Wunused-variable]
   32 |  int i=0;
      |      ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4540 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4540 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4596 KB Output is correct
4 Correct 1043 ms 26172 KB Output is correct
5 Correct 90 ms 19296 KB Output is correct
6 Correct 26 ms 6664 KB Output is correct
7 Correct 322 ms 21344 KB Output is correct
8 Correct 717 ms 25604 KB Output is correct
9 Correct 1366 ms 24344 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4796 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4540 KB Output is correct
13 Correct 1 ms 4544 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 10 ms 4956 KB Output is correct
17 Correct 11 ms 4956 KB Output is correct
18 Correct 15 ms 4952 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4544 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4540 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1052 ms 26168 KB Output is correct
11 Correct 85 ms 19296 KB Output is correct
12 Correct 27 ms 6432 KB Output is correct
13 Correct 333 ms 21356 KB Output is correct
14 Correct 775 ms 25744 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4544 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 10 ms 4956 KB Output is correct
22 Correct 1371 ms 27540 KB Output is correct
23 Correct 1363 ms 24412 KB Output is correct
24 Correct 402 ms 26876 KB Output is correct
25 Correct 403 ms 24384 KB Output is correct
26 Correct 497 ms 28860 KB Output is correct
27 Correct 584 ms 25560 KB Output is correct
28 Correct 699 ms 25292 KB Output is correct
29 Correct 1370 ms 27748 KB Output is correct