Submission #1098473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098473		rahidilbayramli	Robots (IOI13_robots)	C++17	0 / 100	1 ms	444 KiB

robots

#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]);
        sort(all(vect2));
        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])
                i++;
            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";
}*/

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10