| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1098458 | rahidilbayramli | 로봇 (IOI13_robots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "robots.h"
#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define p_b pop_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int i, j;
if(!B)
{
int maxx = 0;
for(i = 0; i < T; i++)
maxx = max(maxx, W[i]);
int mx = 0;
for(i = 0; i < A; i++)
mx = max(mx, X[i]);
if(mx <= maxx)
return -1;
vl vect1, vect2;
for(i = 0; i < T; i++)
vect1.pb(W[i]);
vect1.pb(LLONG_MAX);
sort(all(vect1));
for(i = 0; i < A; i++)
vect2.pb(X[i]);
priority_queue<pll>pq;
i = 0, j = 0;
vl idx[T+5];
while(i < (int)(vect2.size()) && j < (int)(vect1.size()-1))
{
if(vect2[i] >= vect1[j] && vect2[i] < vect1[j+1])
{
idx[j].pb(vect2[i]);
i++;
}
else
j++;
}
map<int, int>mp;
for(i = T - 1; i >= 0; i--)
{
for(auto u : idx[i])
pq.push({0, u});
ll b = pq.top().s;
pq.pop();
mp[b]++;
pq.push({-mp[b], b});
}
maxx = 0;
for(auto u : mp)
maxx = max(maxx, u.s);
return maxx;
}
int n = T;
int w[n+5], s[n+5];
int a = A, b = B;
int x[a+5], y[b+5];
for(i = 1; i <= n; i++)
{
w[i] = W[i-1];
s[i] = S[i-1];
}
for(i = 1; i <= a; i++)
x[i] = X[i-1];
for(i = 1; i <= b; i++)
y[i] = Y[i-1];
set<int>wt[a+5], st[b+5];
set<pii>r[n+5];
for(i = 1; i <= a; i++)
{
for(j = 1; j <= n; j++)
{
if(w[j] < x[i])
{
wt[i].insert(j);
r[j].insert({0, i});
}
}
}
for(i = 1; i <= b; i++)
{
for(j = 1; j <= n; j++)
{
if(s[j] < y[i])
{
st[i].insert(j);
r[j].insert({1, i});
}
}
}
vector<pii>vect;
for(i = 1; i <= n; i++)
{
int sz = (int)(r[i].size());
vect.pb({sz, i});
}
sort(all(vect));
if(vect[0].f == 0)
return -1;
int mx = max(a, b);
set<int>csz[mx+5][2];
for(i = 0; i < (int)vect.size(); i++)
{
int curt = vect[i].s;
int sz1 = INT_MAX, sz2 = INT_MAX, rt = -1, h = -1;
for(auto u : r[curt])
{
int dd = (int)(csz[u.s][u.f].size());
if(dd < sz1)
{
sz1 = dd;
rt = u.s;
h = u.f;
}
else if(dd == sz1)
{
int dg;
if(u.f == 0)
dg = (int)(wt[u.s].size());
else
dg = (int)(st[u.s].size());
if(dg < sz2)
{
sz2 = dg;
rt = u.s;
h = u.f;
}
}
}
csz[rt][h].insert(curt);
if(h == 0)
wt[rt].erase(curt);
else
st[rt].erase(curt);
}
int res = 0;
for(i = 1; i <= a; i++)
{
int dd = (int)(csz[i][0].size());
res = max(res, dd);
}
for(i = 1; i <= b; i++)
{
int dd = (int)(csz[i][1].size());
res = max(res, dd);
}
return res;
}
int main()
{
int A, B, T;
cin >> T >> A >> B;
int X[A], Y[B], W[T], S[T];
for(int i = 0; i < T; i++)
cin >> W[i];
for(int i = 0; i < T; i++)
cin >> S[i];
for(int i = 0; i < A; i++)
cin >> X[i];
for(int i = 0; i < B; i++)
cin >> Y[i];
cout << putaway(A, B, T, X, Y, W, S) << "\n";
}