Submission #993576

#	Time	Username	Problem	Language	Result	Execution time	Memory
993576		Muaath_5	Robots (IOI13_robots)	C++17	14 / 100	1283 ms	23088 KiB

robots

    #include "robots.h"
    #include <bits/stdc++.h>
    using namespace std;
    #ifdef ONPC
    #include"debug.h"
    #else
    #define debug(...) 42
    #endif
    #define ll long long
    #define pii pair<int,int>
    #define pb push_back
    #define sz(a) (int)a.size()
    #define all(a) a.begin(),a.end()
    template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
    template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
    const int mod = 1e9 + 7;
    const int MAXN = 1e6 + 15;
    const int inf = 0x3f3f3f3f;
    const ll INF = 0x3f3f3f3f3f3f3f3f;
     
    int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    	sort(X, X + A);
    	sort(Y, Y + B);
    	int mxW = (A ? X[A - 1] : -1);
    	int mxS = (B ? Y[B - 1] : -1);
    	for (int i = 0; i < T; i++){
    		if (W[i] >= mxW && S[i] >= mxS){
    			return -1;
    		}
    	}
    	vector<pii> robots(T);
    	for (int i = 0; i < T; i++) robots[i] = {W[i], S[i]};
    	sort(all(robots));
    	int lo = 0, hi = T;
    	while (hi - lo > 1){
    		int mi = (lo + hi) / 2;
    		priority_queue<int> pq;
    		int p = 0;
    		for (int i = 0; i < A; i++){
    			while (p < T && robots[p].first < X[i]){
    				pq.push(robots[p].second);
    				p++;
    			}
    			for (int j = 0; j < mi; j++) {
    				if (sz(pq)) pq.pop();
    				else break;
    			}
    		}
    		for (int i = p; i < T; i++) pq.push(robots[i].second);
    		bool ok = 1;
    		for (int i = B - 1; i >= 0; i--){
    			if (sz(pq) == 0) break;
    			if (Y[i] <= pq.top()){
    				ok = 0;
    			}
    			for (int j = 0; j < mi; j++) {
    				if (sz(pq)) pq.pop();
    				else break;
    			}
    		}
    		if (sz(pq) == 0){
    			hi = mi;
    		} else {
    			lo = mi;
    		}
    	}
    	//if (hi == T + 1) hi = -1;
    	return hi;
    }

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:50:12: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   50 |       bool ok = 1;
      |            ^~

• Subtask 1: 0 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10