This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/// dwuy: _,\,,,_\,__,\,,_
#include "robots.h"
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 1000005;
int n, m, t;
int weak[MX];
int small[MX];
pii a[MX];
pii b[MX];
bool ok(int mid){
bitset<MX> vist = 0;
for(int i=1, j=1, cur=0; i<=t; i++){
if(weak[j] <= a[i].fi) continue;
if(j>n) break;
vist[a[i].se] = 1;
if(++cur==mid) j++, cur=0;
}
vector<int> cnt(m+1, 0);
for(int i=1, j=1; i<=t; i++){
if(small[j] <= b[i].fi) continue;
if(j>m) break;
if(!vist[b[i].se]){
vist[b[i].se] = 1;
cnt[j]++;
if(cnt[j]==mid) j++;
}
}
for(int i=1, j=1, k=1; i<=t; i++){
while(j<=m && cnt[j]==mid) j++;
if(j > m) break;
if(small[j] <= b[i].fi) continue;
if(vist[b[i].se]){
while(k<=t && (a[k].fi>=weak[1] || vist[a[k].se])) k++;
if(k>t) continue;
vist[a[k].se] = 1;
cnt[j]++;
}
}
for(int i=1; i<=t; i++) if(!vist[i]) return 0;
return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
tie(n, m, t) = {A, B, T};
for(int i=0; i<n; i++) weak[i+1] = X[i];
for(int i=0; i<m; i++) small[i+1] = Y[i];
for(int i=0; i<t; i++){
a[i+1] = {W[i], i+1};
b[i+1] = {S[i], i+1};
}
sort(weak+1, weak+1+n, greater<int>());
sort(small+1, small+1+m, greater<int>());
sort(a+1, a+1+t, greater<pii>());
sort(b+1, b+1+t, greater<pii>());
int ans = -1;
for(int lo=1, hi=t; lo<=hi;){
int mid = (lo+hi)>>1;
if(ok(mid)) ans = mid, hi = mid - 1;
else lo = mid + 1;
}
return ans;
}
# | 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... |