Submission #1098412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098412		rahidilbayramli	Robots (IOI13_robots)	C++17	39 / 100	204 ms	65536 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 n = T, a = A;
        int w[n+5], sss[n+5];
        int x[a+5];
        int i, j;
        for(i = 1; i <= n; i++)
        {
            w[i] = W[i-1];
            sss[i] = S[i-1];
        }
        for(i = 1; i <= a; i++)
            x[i] = X[i-1];
        set<int>wt[a+5], r[n+5], csz[a+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(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;
        for(i = 0; i < (int)vect.size(); i++)
        {
            int curt = vect[i].s;
            int sz1 = INT_MAX, sz2 = INT_MAX, rt = -1;
            for(auto u : r[curt])
            {
                int dd = (int)(csz[u].size());
                if(dd < sz1)
                {
                    sz1 = dd;
                    rt = u;
                }
                else    if(dd == sz1)
                {
                    int dg = (int)(wt[u].size());
                    if(dg < sz2)
                    {
                        sz2 = dg;
                        rt = u;
                    }
                }
            }
            csz[rt].insert(curt);
            wt[rt].erase(curt);
        }
        int res = 0;
        for(i = 1; i <= a; i++)
        {
            int dd = (int)(csz[i].size());
            res = max(res, dd);
        }
        return res;
    }
    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";
}*/

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:26:21: warning: variable 'sss' set but not used [-Wunused-but-set-variable]
   26 |         int w[n+5], sss[n+5];
      |                     ^~~

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