| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 619866 | M_W | 로봇 (IOI13_robots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ii pair<int, int>
#define ar array<int, 3>
using namespace std;
bitset<1000001> mark;
struct cmp{
bool operator() (const ar &a, const ar &b) const{
return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
}
};
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
vector<ii> v, item_w, item_s;
for(int i = 0; i < A; i++) v.push_back({X[i], 1});
for(int i = 0; i < B; i++) v.push_back({Y[i], 2});
sort(v.begin(), v.end());
for(int i = 0; i < T; i++){
item_w.push_back({W[i], i});
item_s.push_back({S[i], i});
}
sort(item_w.begin(), item_w.end());
sort(item_s.begin(), item_s.end());
int l = 1, r = T; bool ans = false;
while(l < r){
int mid = (l + r) >> 1;
for(int i = 0; i <= T; i++) mark[i] = 0;
priority_queue<ar, vector<ar>, cmp> wt, sz;
int idx_w = 0, idx_s = 0;
// printf("T = %d\n", mid);
for(auto [x, t] : v){
int cnt = 0;
if(t == 1){
while(idx_w < T && item_w[idx_w].first < x){
wt.push({item_w[idx_w].first, S[item_w[idx_w].second], item_w[idx_w].second});
idx_w++;
}
while(!wt.empty()){
auto [w, s, i] = wt.top();
wt.pop();
if(mark[i]) continue;
if(w >= x || cnt >= mid) break;
mark[i] = 1;
// printf("bot weak %d take %d (%d)\n", x, w, i);
cnt++;
}
}
else{
while(idx_s < T && item_s[idx_s].first < x){
sz.push({item_s[idx_s].first, W[item_s[idx_s].second], item_s[idx_s].second});
idx_s++;
}
while(!sz.empty()){
auto [s, w, i] = sz.top();
sz.pop();
if(mark[i]) continue;
if(s >= x || cnt >= mid) break;
mark[i] = 1;
// printf("bot small %d take %d (%d)\n", x, s, i);
cnt++;
}
}
}
while(idx_w < T){
wt.push({item_w[idx_w].first, S[item_w[idx_w].second], item_w[idx_w].second});
idx_w++;
}
while(idx_s < T){
sz.push({item_s[idx_s].first, W[item_s[idx_s].second], item_s[idx_s].second});
idx_s++;
}
while(!sz.empty() && mark[sz.top()[2]]) sz.pop();
while(!wt.empty() && mark[wt.top()[2]]) wt.pop();
if(sz.empty() && wt.empty()){
ans = true;
r = mid;
}
else l = mid + 1;
}
if(!ans) return -1;
return l;
}