| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 478225 | joshjms | 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;
#define ll long long
#define ld long double
#define int long long
#define pb push_back
#define fi first
#define se second
#define konaqua ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define otsuaqua exit(0);
#define debug(x) cout << #x << " => " << x << "\n"
#define all(x) x.begin(), x.end()
#define sp " "
/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/
const ll INFF = 1e18 + 5;
const ll INF = 1e10 + 5;
const int MX = 1e6 + 5;
const int MXL = 105;
const int mod = 1e9 + 7;
const double ERROR = 1e-8;
const ld pi = 3.14159265358979323846;
const int set_inf = 0x3f3f3f3f;
int a, b, t;
int l, r, md, ans = INFF;
pair <int,int> toys[1000005];
int x[50005], y[50005];
set <pair<int,int>> st;
bool vis[1000005];
int sr[50005], wr[50005], it;
bool check(){
memset(vis, 0, sizeof(vis));
memset(wr, 0, sizeof(wr));
memset(sr, 0, sizeof(sr));
st.clear();
for(int i = 0; i < b; i++)
st.insert({y[i], i});
for(int i = t - 1; i >= 0; i--){
if(st.empty()) break;
auto idx = st.lower_bound({toys[i].se, 0});
if(idx == st.end()) continue;
pair <int,int> p = *idx;
vis[i] = 1;
sr[p.se]++;
if(sr[p.se] >= md) st.erase(idx);
}
it = 0;
for(int i = 0; i < t; i++){
if(vis[i]) continue;
while((toys[i].fi > x[it] || wr[it] >= md) && it < a) it++;
if(it >= a) break;
vis[i] = 1;
wr[it]++;
}
for(int i = 0; i < t; i++){
if(!vis[i]) return 0;
}
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 = 0; i < t; i++)
toys[i] = make_pair(W[i], S[i]);
sort(toys, toys + t);
for(int i = 0; i < a; i++)
x[i] = X[i];
sort(x, x + a);
for(int i = 0; i < b; i++)
y[i] = Y[i];
sort(y, y + b);
l = 1, r = t;
while(l <= r){
md = (l + r) / 2;
if(check())
r = md - 1, ans = min(ans, md);
else l = md + 1;
}
return ans;
}
// void solve(){
// 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 >> toys[i].fi >> toys[i].se;
// sort(toys, toys + t);
// sort(x, x + a);
// sort(y, y + b);
// l = 1, r = t;
// while(l <= r){
// md = (l + r) / 2;
// if(check())
// r = md - 1, ans = min(ans, md);
// else l = md + 1;
// }
// cout << ans << "\n";
// }
// signed main(){
// konaqua;
// solve();
// otsuaqua;
// }
/*
3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
*/