Submission #260995

#	Time	Username	Problem	Language	Result	Execution time	Memory
260995		SamAnd	Robots (IOI13_robots)	C++17	76 / 100	1857 ms	20216 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];

bool stg(int q)
{
    multiset<pair<int, int> > s;
    for (int i = 0; i < xn; ++i)
    {
        s.insert(m_p(x[i], q));
    }

    vector<int> v;
    for (int i = n - 1; i >= 0; --i)
    {
        auto it = s.upper_bound(m_p(a[i].x, N));
        if (it == s.end())
        {
            v.push_back(a[i].y);
            continue;
        }
        pair<int, int> u = *it;
        s.erase(it);
        u.se--;
        if (u.se)
            s.insert(u);
    }

    vector<int> qq(yn);
    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 (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);
    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:104:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int ans;
         ^~~

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