이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
vector<pair<int,int>> T;
bool check(int a, int b, int t, int X[], int Y[], int W[], int S[], int cp) {
auto ta = T;
multiset<pair<int,int>> bt;
for (int i=0; i<b; i++) bt.insert({Y[i], cp});
for (int i=0; i<t; i++) {
auto it = bt.lower_bound({ta[i].second, 1});
if (it == bt.end()) continue;
pair<int,int> q = *it;
bt.erase(bt.find(q)); q.second--; if (q.second) bt.insert(q);
ta[i].first = -1;
}
vector<pair<int,int>> tb;
for (int i=0; i<t; i++) {if (ta[i].first!=-1) tb.push_back({ta[i].second, ta[i].first});}
sort(tb.begin(), tb.end());
multiset<pair<int,int>> at;
for (int i=0; i<a; i++) at.insert({X[i], cp});
for (int i=0; i<tb.size(); i++) {
auto it = at.lower_bound({tb[i].second, 1});
if (it == at.end()) return 0;
pair<int,int> q = *it;
at.erase(at.find(q)); q.second--; if (q.second) at.insert(q);
}
return 1;
}
int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[]){
for (int i=0; i<t; i++) W[i]++;
for (int i=0; i<t; i++) S[i]++;
sort(X, X+a); sort(Y, Y+b);
for (int i = 0; i < t; i++) T.push_back(make_pair(W[i],S[i]));
sort(T.begin(),T.end(), greater<pair<int,int>>());
int l = 1, r = t+1;
while (l<r) {
int m = (l+r)/2;
if (check(a,b,t,X,Y,W,S,m)) r = m;
else l = m+1;
}
if (l==r+1) return -1; else return l;
/*
if (W[t-1] > X[a-1]) return -1;
int mc = a-1; int toy = t-1; int cnt = 0;
vector<int> exc(a, 0);
while (mc){
while (X[mc-1] < W[toy]) toy--, cnt++;
exc[mc] = cnt; cnt = 0; mc--;
}
exc[mc] = toy+1;
// for (int i=0; i<a; i++) cout<<exc[i]<<' ';
int ans = 1;
for (int i=a-2; i>=0; i--) exc[i] = exc[i+1]+exc[i];
for (int i=0; i<a; i++) ans = max(ans, (exc[i]+a-1-i)/(a-i));
*/
}
/*
5
0
9
1 5 6 8 30
5 0
5 0
3 0
5 0
8 0
12 0
14 0
19 0
20 0
*/
컴파일 시 표준 에러 (stderr) 메시지
robots.cpp: In function 'bool check(int, int, int, int*, int*, int*, int*, int)':
robots.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i=0; i<tb.size(); i++) {
| ~^~~~~~~~~~
# | 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... |