Submission #1098289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098289		rahidilbayramli	Robots (IOI13_robots)	C++17	39 / 100	181 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 n = T;
    int w[n+5], s[n+5];
    int a = A, b = B;
    int x[a+5], y[b+5];
    int i, j;
    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;
}

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