Submission #281737

#	Time	Username	Problem	Language	Result	Execution time	Memory
281737		Kastanda	Robots (IOI13_robots)	C++11	0 / 100	271 ms	13292 KiB

robots

// M
#include<bits/stdc++.h>
#include "robots.h"
using namespace std;
const int N = 50004, MXN = 1e6 + 3;
int n, m, k, X[N], Y[N], W[MXN], S[MXN], PS[N], C[N];
vector < int > V[N];
priority_queue < int > Pq;
inline bool Solve(int md)
{
        int Cnt = 0; Pq = {};
        memset(C, 0, sizeof(C));
        memset(PS, 0, sizeof(PS));

        auto Push = [&](int val) {
                if (!C[val])
                        Pq.push(-val);
                C[val] ++;
        };
        auto Pop = [&]() {
                int val = -Pq.top();
                C[val] --;
                if (!C[val])
                        Pq.pop();
                return val;
        };

  assert(m == 0);
        for (int i = n; i >= 0; i --)
        {
                if (i < n)
                        Cnt += md;
                Cnt -= (int)V[i].size();
          if (Cnt < 0)
            return 0;
        }
        return 1;
}
int putaway(int _n, int _m, int _k, int _X[], int _Y[], int _W[], int _S[])
{
        n = _n; m = _m; k = _k;
        for (int i = 0; i < n; i ++)
                X[i] = _X[i];
        for (int i = 0; i < m; i ++)
                Y[i] = _Y[i];
        for (int i = 0; i < k; i ++)
                W[i] = _W[i], S[i] = _S[i];
        sort(X, X + n);
        sort(Y, Y + m);
        for (int i = 0; i < k; i ++)
        {
                int jx = upper_bound(X, X + n, W[i]) - X;
                int jy = upper_bound(Y, Y + m, S[i]) - Y;
                V[jx].push_back(jy);
        }
        for (int i = 0; i <= n; i ++)
                sort(V[i].begin(), V[i].end());

        if (!Solve(k))
                return -1;

        int le = 0, ri = k, md;
        while (ri - le > 1)
        {
                md = (le + ri) >> 1;
                if (Solve(md))
                        ri = md;
                else
                        le = md;
        }
        return ri;
}

Compilation message (stderr)

robots.cpp: In function 'bool Solve(int)':
robots.cpp:15:14: warning: variable 'Push' set but not used [-Wunused-but-set-variable]
   15 |         auto Push = [&](int val) {
      |              ^~~~
robots.cpp:20:14: warning: variable 'Pop' set but not used [-Wunused-but-set-variable]
   20 |         auto Pop = [&]() {
      |              ^~~

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