제출 #260987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260987		SamAnd	로봇 (IOI13_robots)	C++17	0 / 100	1 ms	384 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, 0));
        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);
    }

    s.clear();
    for (int i = 0; i < yn; ++i)
    {
        s.insert(m_p(y[i], q));
    }

    sort(all(v));
    reverse(all(v));
    for (int i = 0; i < sz(v); ++i)
    {
        auto it = s.upper_bound(m_p(v[i], 0));
        if (it == s.end())
            return false;
        pair<int, int> u = *it;
        s.erase(it);
        u.se--;
        if (u.se)
            s.insert(u);
    }
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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