| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 839039 | Cookie | 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<bits/stdc++.h>
#include "robots.h"
using namespace std;
ifstream fin("susss.txt");
ofstream fout("res.txt");
#define forr(i, a, b) for(int i = a; i < b; i++)
#define pb push_back
#define vt vector
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define sz(v) (int)v.size()
const int mxn = 1e6, inf = 1e9, mod = 1e9 + 7, mxm = 50005;
int t, a, b;
pii p[mxn + 1];
int x[mxm + 1], y[mxm + 1], cnt[mxm + 1];
bool good[mxn + 1];
bool ck(int mid){
set<pair<int, int>>s;
for(int i = 1; i <= b; i++){
cnt[i] = mid; s.insert(make_pair(y[i], i));
}
for(int i = t; i >= 1; i--){
good[i] = 0;
auto it = s.lower_bound(make_pair(p[i].se + 1, -1));
if(it != s.end()){
good[i] = 1;
int id = (*it).second;
cnt[id]--;
if(cnt[id] == 0){
s.erase(make_pair(y[id], id));
}
}
}
int bestid = a, cntt = mid;
for(int i = t; i >= 1; i--){
if(!good[i]){
if(p[i].fi >= x[bestid])return(0);
cntt--;
if(cntt == 0){
bestid--; cntt = mid;
}
}
}
return(1);
}
int putaway(int A,int B,int T, int X[],int Y[],int W[],int S[]);
a = A; b = B; t = T;
for(int i = 1; i <= a; i++)x[i] = X[i];
for(int i = 1; i <= b; i++)y[i] = Y[i];
sort(x + 1, x + a + 1); sort(y + 1, y + b + 1);
for(int i = 1; i <= t; i++){
p[i].fi = W[i]; p[i].se = S[i];
}
sort(p + 1, p + t + 1);
int l = 1, r = t, ans = -1;
while(l <= r){
int mid = (l + r) >> 1;
if(ck(mid)){
ans = mid; r = mid - 1;
}else{
l = mid + 1;
}
}
return(ans);
}