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<bits/stdc++.h>
#include"robots.h"
#define wei first
#define sz second
using namespace std;
const int N = 1e6 + 2;
pair<int, int> c[N];
int a, b, t, x[N], y[N];
bool check(int h)
{
priority_queue<int, vector<int>, greater<int>> q;
vector<int> xetb;
int cur = a - 1, cnt = h;
for(int i = t - 1; i >= 0; i--)
{
if(cur == -1)
{
if(a == 0)
xetb.push_back(c[i].sz);
else
{
q.push(c[i].sz);
xetb.push_back(q.top());
q.pop();
}
continue;
}
if(c[i].wei < x[cur])
{
q.push(c[i].sz);
cnt--;
if(cnt == 0)
cur--, cnt = h;
}
else
{
if(cur < a - 1)
{
q.push(c[i].sz);
xetb.push_back(q.top());
q.pop();
}
else
xetb.push_back(c[i].sz);
}
}
sort(xetb.begin(), xetb.end());
cur = 0, cnt = h;
for(auto i : xetb)
{
if(cur == b)
return false;
if(i < y[cur])
{
cnt--;
if(cnt == 0)
cur++, cnt = h;
}
else
{
while(i >= y[cur] && cur < b)
cur++, cnt = h - 1;
if(cur == b)
return false;
}
}
return true;
}
int putaway(int ha, int hb, int ht, int hx[], int hy[], int W[], int S[])
{
a = ha;
b = hb;
t = ht;
for(int i = 0; i < a; i++)
x[i] = hx[i];
for(int i = 0; i < b; i++)
y[i] = hy[i];
sort(x + 0, x + a + 0);
sort(y + 0, y + b + 0);
for(int i = 0; i < t; i++)
c[i] = make_pair(W[i], S[i]);
sort(c + 0, c + t + 0);
int ans = -1, low = 1, high = t, mid;
while(low <= high)
{
mid = (low + high) / 2;
if(check(mid))
{
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
//int main ()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
// cin >> a >> b >> t;
// for(int i = 0; i < a; i++)
// cin >> x[i];
// for(int i = 0; i < b; i++)
// cin >> y[i];
// for(int i = 0; i < t; i++)
// cin >> c[i].wei;
// for(int i = 0; i < t; i++)
// cin >> c[i].sz;
// return 0;
//}
# | 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... |