| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 109164 | dantoh000 | Robots (IOI13_robots) | C++14 | 0 ms | 0 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;
typedef pair<int,int> ii;
int w[1000005], s[1000005];
bool cmpw(int a, int b){
if (w[a] != w[b]) return w[a] < w[b];
else return s[a] < s[b];
}
bool cmps(int a, int b){
return s[a] <= s[b];
}
bool cando(int x, int A, int B, int T, int X[], int Y[], int W[], int S[]){
//printf("\t\t\t\tTesting %d\n",x);
vector<int> v(T);
for (int i = 0; i < T; i++) v[i] = i;
sort(v.begin(),v.end(),cmpw);
int curT = 0, curA = 0;
priority_queue<int> pq;
while (curT < T && curA < A){
//printf("toy %d weight %d robot %d\n",v[curT],W[v[curT]],curA);
if (X[curA] <= W[v[curT]]){
int num = 0;
while (num++ < x && pq.size()){
//printf("robot %d takes %d weight %d\n",curA,pq.top().second,pq.top().first);
pq.pop();
}
curA++;
}
else{
pq.push(S[v[curT]]);
curT++;
}
}
while (curA++ < A){
int num = 0;
while (num++ < x && pq.size()){
//printf("robot %d takes %d size %d\n",curA,pq.top().second,pq.top().first);
pq.pop();
}
}
while (curT < T){
//printf("toy %d not taken by weight\n",v[curT]);
pq.push(S[v[curT++]]);
}
int curB = B-1;
while (curB && pq.size()){
//printf("toy %d size %d robot %d\n",v2[curT],S[v2[curT]],curB);
if (Y[curB] <= pq.top()) return false;
else{
int num = 0;
while (num++ < x && pq.size()){
//printf("robot %d takes %d size %d\n",curB,pq.top().second,pq.top().first);
pq.pop();
}
curB--;
}
}
return pq.empty();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
for (int i = 0; i < T; i++){
w[i] = W[i];
s[i] = S[i];
}
sort(X,X+A);
sort(Y,Y+B);
int lo = 0, hi = T+1;
while (lo + 1 < hi){
//printf("%d %d\n",lo,hi);
int mid = (lo+hi)/2;
if (cando(mid,A,B,T,X,Y,W,S)){
hi = mid;
}
else lo = mid;
}
if (lo + 1 == hi){
//printf("%d %d\n",lo,hi);
if (cando(lo,A,B,T,X,Y,W,S)) hi = lo;
else lo = hi;
}
if (lo == T+1) return -1;
return lo;
}
#include <stdio.h>
#include <stdlib.h>
//#include "robots.h"
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_A 50000
#define MAX_B 50000
#define MAX_T 500000
static int X[MAX_A];
static int Y[MAX_B];
static int W[MAX_T];
static int S[MAX_T];
int main() {
int A, B, T, i;
int res;
//FILE *f = fopen("robots.in", "r");
//if (!f)
// fail("Failed to open input file.");
res = scanf("%d", &A);
if (res != 1)
fail("Failed to read A from input file.");
if (A < 0 || A > MAX_A)
fail("A is out of bounds.");
res = scanf( "%d", &B);
if (res != 1)
fail("Failed to read B from input file.");
if (B < 0 || B > MAX_B)
fail("B is out of bounds.");
res = scanf("%d", &T);
if (res != 1)
fail("Failed to read T from input file.");
if (T < 1 || T > MAX_T)
fail("T is out of bounds.");
for (i = 0; i < A; i++) {
res = scanf( "%d", &X[i]);
if (res != 1)
fail("Failed to read data from input file.");
}
for (i = 0; i < B; i++) {
res = scanf( "%d", &Y[i]);
if (res != 1)
fail("Failed to read data from input file.");
}
for (i = 0; i < T; i++) {
res = scanf("%d%d", &W[i], &S[i]);
if (res != 2)
fail("Failed to read data from input file.");
}
//fclose(f);
int answer = putaway(A, B, T, X, Y, W, S);
printf("%d\n", answer);
return 0;
}