Submission #260999

#	Time	Username	Problem	Language	Result	Execution time	Memory
260999		SamAnd	Robots (IOI13_robots)	C++17	100 / 100	433 ms	27184 KiB

robots

#include "robots.h"
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 1000006;

struct ban
{
    int x, y;
};
bool soy(const ban& a, const ban& b)
{
    return a.y < b.y;
}
bool sox(const ban& a, const ban& b)
{
    return a.x < b.x;
}

int n;
ban a[N];

int xn, yn;
int x[N], y[N];

int qq[N];

int u[N];
int p[N];

int fi(int x)
{
    if (x == p[x])
        return x;
    return p[x] = fi(p[x]);
}

bool stg(int q)
{
    for (int i = 0; i < xn; ++i)
    {
        qq[i] = q;
    }

    for (int i = 0; i <= xn; ++i)
        p[i] = i;

    vector<int> v;
    for (int i = n - 1; i >= 0; --i)
    {
        int j = u[i];
        bool z = false;
        while (1)
        {
            if (j == xn)
                break;
            if (qq[j])
            {
                --qq[j];
                z = true;
                break;
            }
            if (j == p[j])
                p[j] = j + 1;
            j = fi(j);
        }
        if (!z)
            v.push_back(a[i].y);
    }

    for (int i = 0; i < yn; ++i)
    {
        qq[i] = q;
    }
    int j = yn - 1;
    for (int i = 0; i < sz(v); ++i)
    {
        while (j != -1 && qq[j] == 0)
            --j;
        if (j == -1)
            return false;
        if (y[j] <= v[i])
            return false;
        --qq[j];
    }
    return true;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    xn = A;
    yn = B;
    for (int i = 0; i < xn; ++i)
        x[i] = X[i];
    for (int i = 0; i < yn; ++i)
        y[i] = Y[i];

    n = T;
    for (int i = 0; i < n; ++i)
    {
        a[i].x = W[i];
        a[i].y = S[i];
    }

    sort(x, x + xn);
    sort(y, y + yn);

    for (int i = 0; i < n; ++i)
    {
        if (xn && a[i].x < x[xn - 1])
            continue;
        if (yn && a[i].y < y[yn - 1])
            continue;
        return -1;
    }

    sort(a, a + n, soy);
    for (int i = 0; i < n; ++i)
    {
        u[i] = upper_bound(x, x + xn, a[i].x) - x;
    }

    int l = 1, r = n;
    int ans;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (stg(m))
        {
            ans = m;
            r = m - 1;
        }
        else
            l = m + 1;
    }
    return ans;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:131:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int ans;
         ^~~

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