| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 198983 | maximath_1 | Robots (IOI13_robots) | C++11 | 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;
#define ll long long
int n, a, b;
pair<int, int> v[1000005];
int wt[1000005], sz[1000005];
vector<int>vv[1000005];
bool ok(int x){
int sisa=0;
vector<int>isi;
priority_queue<int>pq;
for(int i=0; i<vv[0].size(); i++)
isi.push_back(vv[0][i]);
for(int i=1; i<=a; i++){
for(int j=0; j<vv[i].size(); j++)
pq.push(vv[i][j]);
int siz=vv[i].size();
if(sisa>=siz-x) sisa-=siz-x;
else{
for(int j=1; j<=siz-x-sisa; j++){
if(pq.empty()) return false;
isi.push_back(pq.top()); pq.pop();
}
sisa=0;
}
}
sort(isi.begin(), isi.end());
for(int i=0; i<isi.size(); i++){
int tmp=i/a+1;
if(tmp>b || tmp>isi[i]) return false;
}
return true;
}
int putaway(int _a, int _b, int _t, int x[], int y[], int w[], int s[]){
n=_t;
a=_a; b=_b;
sort(x, x+a); sort(y, y+b);
for(int i=0; i<n; i++){
v[i]={w[i], s[i]};
if(w[i]>=x[a-1] && s[i]>=y[b-1])
return -1;
}
for(int i=0; i<n; i++){
int l=0, r=a-1, md;
while(l<=r){
md=(l+r)>>1;
if(v[i].first<x[md]){
wt[i]=a-md;
r=md-1;
}else l=md+1;
}
l=0, r=b-1;
while(l<=r){
md=(l+r)>>1;
if(v[i].second<y[md]){
sz[i]=b-md;
r=md-1;
}else l=md+1;
}
vv[wt[i]].push_back(sz[i]);
}
int ans=-1;
int l=1, r=n, md;
while(l<=r){
md=(l+r)>>1;
if(ok(md)){
ans=md; r=md-1;
}else l=md+1;
}
return ans;
}