oj.uz

Submission #964955

# Submission time Handle Problem Language Result Execution time Memory
964955 2024-04-17T19:07:56 Z Acanikolic Robots (IOI13_robots) C++14
53 / 100
 568 ms 31964 KB 
#include <bits/stdc++.h>
		 		
#include "robots.h"	 		
		 		
//#define int long long 
		 
#define pb push_back 
		
#define F first
		 
#define S second
		 
using namespace std;
		 
const int N = 1000000 + 10;
		 
const int mod = 1e9 + 7;
		 
const int inf = 1e9; 	

bool check(int A,int B,int T,vector<int>X,vector<int>Y,vector<pair<int,int>>W,vector<pair<int,int>>S,int mid) {
	vector<bool>vis(T,false);
	priority_queue<int>pq;
	int ptr = -1;
	for(int i = 0; i < T; i++) {
		if(pq.empty() && ptr + 1 < A && X[ptr + 1] > W[i].F) {
			for(int j = 0; j < mid; j++) {
				pq.push(X[ptr + 1]);
			}
			ptr += 1;
		}
		if(mid == 3 && i == 1) {
			//cout << "debug:" << X[ptr + 1] << " " << W[i].F << " " << W[i].S << endl; 
		}
		if(pq.empty()) continue;
		vis[W[i].S] = true;
		pq.pop();
	}
	if(mid == 3) {
		//for(int i = 0; i < T; i++) if(vis[i]) cout << "dbg:::" << i << endl;
		//cout << endl;
	}
	while(pq.size()) pq.pop();
	ptr = -1;
	for(int i = 0; i < T; i++) {
		if(vis[S[i].S]) continue;
		if(pq.empty() && ptr + 1 < B && Y[ptr + 1] > S[i].F) {
			for(int j = 0; j < mid; j++) {
				pq.push(Y[ptr + 1]);
			}
			ptr += 1;
		}
		if(pq.empty()) continue;
		vis[S[i].S] = true;
		pq.pop();
	}
	bool ok = true;
	for(int i = 0; i < T; i++) if(!vis[i]) ok = false;
	if(mid == 3) {
	//	for(int i = 0; i < T; i++) if(vis[i]) cout << "dbg:::" << i << endl;
	}
	if(ok) return true;
	while(pq.size()) pq.pop();
	for(int i = 0; i < T; i++) vis[i] = false;
	ptr = -1;
	for(int i = 0; i < T; i++) {
		if(pq.empty() && ptr + 1 < B && Y[ptr + 1] > S[i].F) {
			for(int j = 0; j < mid; j++) {
				pq.push(Y[ptr + 1]);
			}
			ptr += 1;
		}
		if(pq.empty()) continue;
		vis[S[i].S] = true;
		pq.pop();
	}
	while(pq.size()) pq.pop();
	ptr = -1;
	for(int i = 0; i < T; i++) {
		if(vis[W[i].S]) continue;
		if(pq.empty() && ptr + 1 < A && X[ptr + 1] > W[i].F) {
			for(int j = 0; j < mid; j++) {
				pq.push(X[ptr + 1]);
			}
			ptr += 1;
		}
		if(pq.empty()) continue;
		vis[W[i].S] = true;
		pq.pop();
	}
	ok = true;
	for(int i = 0; i < T; i++) if(!vis[i]) ok = false;
	return ok;
} 

int putaway(int A, int B, int T, int* x, int* y, int* W, int* S) {
	vector<int>X(A);
	vector<int>Y(B);
	vector<pair<int,int>>w(T);
	vector<pair<int,int>>s(T);
	for(int i = 0; i < T; i++) {
		w[i] = {W[i],i};
		s[i] = {S[i],i};
	}
	for(int i = 0; i < A; i++) X[i] = x[i];
	for(int i = 0; i < B; i++) Y[i] = y[i];
	sort(X.begin(),X.end());
	sort(Y.begin(),Y.end());
	sort(w.begin(),w.end());
	sort(s.begin(),s.end());
	reverse(X.begin(),X.end());
	reverse(Y.begin(),Y.end());
	reverse(w.begin(),w.end());
	reverse(s.begin(),s.end());
	int l = 1, r = max(A,B),ans = -1;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(check(A,B,T,X,Y,w,s,mid)) {
			ans = mid;
			r = mid - 1;
		}else {
			l = mid + 1;
		}
	}
	return ans;
}

Subtask #1
14.0 / 14.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 4444 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 4444 KB Output is correct
4 Correct 345 ms 31964 KB Output is correct
5 Correct 550 ms 31888 KB Output is correct
6 Correct 38 ms 8028 KB Output is correct
7 Correct 335 ms 29528 KB Output is correct
8 Correct 358 ms 31708 KB Output is correct
9 Correct 309 ms 31388 KB Output is correct

Subtask #3
25.0 / 25.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 4444 KB Output is correct
6 Correct 1 ms 4444 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 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 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 4444 KB Output is correct

Subtask #4
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 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 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 4440 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4540 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Incorrect 6 ms 5028 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 10.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 4544 KB Output is correct
6 Correct 1 ms 4444 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 391 ms 31920 KB Output is correct
11 Correct 568 ms 31792 KB Output is correct
12 Correct 36 ms 7888 KB Output is correct
13 Correct 317 ms 29536 KB Output is correct
14 Correct 339 ms 31696 KB Output is correct
15 Correct 1 ms 4540 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4452 KB Output is correct
21 Incorrect 6 ms 4956 KB Output isn't correct
22 Halted 0 ms 0 KB -