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;
const int Nmax = 50005, Mmax = 1e6 + 5;
int x[Mmax], y[Mmax];
class AIB
{
int n, a[Nmax];
int ub(int x) { return (x&(-x)); }
public:
void set_size(int N) { n = N + 1; }
int query(int x)
{
int ans = 0;
for(++x; x; x-=ub(x)) ans += a[x];
return ans;
}
void update(int x)
{
for(++x; x <= n; x+=ub(x)) a[x]++;
}
} aib;
int cbin(int a[], int n, int x)
{
int st = 0, dr = n - 1, mid;
while(st <= dr)
{
mid = (st + dr) / 2;
if(a[mid] > x) st = mid+1;
else dr = mid-1;
}
return dr + 1;
}
bool cmp(int a, int b)
{
if(x[a] == x[b]) return y[a] < y[b];
return x[a] < x[b];
}
int upp(int x, int y) { if(x % y) return x / y + 1; return x / y; }
int putaway(int A, int B, int N, int W[], int S[], int X[], int Y[])
{
int i;
sort(W, W+A); reverse(W, W+A);
sort(S, S+B); reverse(S, S+B);
for(i=0; i<N; ++i)
{
x[i] = cbin(W, A, X[i]);
y[i] = cbin(S, B, Y[i]);
if(x[i] == 0 && y[i] == 0) return -1;
}
vector<int> ord;
for(i=0; i<N; ++i) ord.push_back(i);
sort(ord.begin(), ord.end(), cmp);
int ans = 0, pos;
aib.set_size(B);
for(i=0; i<ord.size(); ++i)
{
pos = ord[i];
aib.update(y[pos]);
if(i + 1 < ord.size() && x[pos] == x[ord[i+1]] && y[pos] == y[ord[i+1]]) continue;
int act = aib.query(y[pos]);
ans = max(ans, upp(act, x[pos] + y[pos]));
}
return ans;
}
Compilation message (stderr)
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:71:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<ord.size(); ++i)
~^~~~~~~~~~~
robots.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + 1 < ord.size() && x[pos] == x[ord[i+1]] && y[pos] == y[ord[i+1]]) continue;
~~~~~~^~~~~~~~~~~~
# | 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... |