# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
80939 | wzy | Robots (IOI13_robots) | C++11 | 3061 ms | 44372 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
// think about the toys as points (W[i] , S[i]) , robots as lines :
// robot A type is a vertical line in X[i]
// robot B type is a horizontal line in Y[i]
// let R[i] be the leftmost type A robot that dominate
vector<pii> hold[2][50005];
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
vector<pii> vert, hori;
for(int i = 0 ; i < A ; i++){
vert.push_back(pii(X[i] , i));
}
for(int i = 0 ; i < B; i++){
hori.push_back(pii(Y[i] , i));
}
sort(vert.begin() , vert.end());
sort(hori.begin() , hori.end());
for(int i = 0 ; i < T ; i++){
int l = 0 , r = vert.size();
r--;
int ansj = -1;
while(l<=r){
int mid = (l+r)/2;
if(vert[mid].F > W[i]){
ansj = mid;
r = mid - 1;
}
else l = mid + 1;
}
if(ansj>=0){
hold[0][ansj].push_back(pii(S[i] ,i));
}
l = 0 , r = hori.size();
r--;
ansj = -1;
while(l<=r){
int mid = (l+r)/2;
if(hori[mid].F > S[i]){
ansj = mid;
r = mid - 1;
}
else l = mid + 1;
}
if(ansj>=0){
hold[1][ansj].push_back(pii(W[i] ,i));
}
}
int l = 1 , r = (int) 1e6;
int ansj = -1;
while(l<=r){
int mid = (l+r)/2;
bool can = true;
set<int> used;
// solve now
// pega os caras pra X
priority_queue<pii> pq;
for(int i = 0 ; i < A ; i++){
for(int j = 0 ; j < hold[0][i].size() ; j++) pq.push(hold[0][i][j]);
int cnt = mid;
while(cnt-- && pq.size()){
pii u = pq.top();
pq.pop();
used.insert(u.S);
}
}
while(!pq.empty()) pq.pop();
for(int i = 0 ; i < B ; i++){
for(int j = 0 ; j < hold[1][i].size() ; j++){
if(used.count(hold[1][i][j].S)) continue;
pq.push(hold[1][i][j]);
}
int cnt = mid;
while(cnt-- && pq.size()){
pii u = pq.top();
pq.pop();
used.insert(u.S);
}
}
if(used.size() != T) can = false;
if(can){
ansj = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ansj;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |