Submission #135941

#	Time	Username	Problem	Language	Result	Execution time	Memory
135941		Talant	Robots (IOI13_robots)	C++17	14 / 100	680 ms	28332 KiB

robots

#include "robots.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

#define sc second
#define fr first
#define mk make_pair
#define pb push_back

using namespace std;

const int N = (1e6 + 5);
const int inf = (1e9 + 7);

int a,b,n;
int x[N],y[N],w[N],s[N];
int mxw,mxs;
int u[N];

vector <pair<int,int> > v;
priority_queue<int> q;
vector <int> vec;

bool check (int cur) {
      int l = a;
      q = priority_queue <int> ();
      vec.clear();
      for (int i = 1; i <= b; i ++) u[i] = 0;

      for (int i = n - 1; i >= 0;) {
            if (v[i].fr < x[l] && l > 0) {
                  for (int j = i; j >= max(0,i - cur + 1); j --)
                        q.push(-v[j].sc);
                  i -= cur;
                  l --;
            }
            else {
                  q.push(-v[i].sc);
                  vec.pb(-q.top());
                  q.pop();
                  i --;
            }
      }
      l = b;
      sort(vec.rbegin(),vec.rend());

      for (int i = 0; i < vec.size(); i ++) {
            if (l == 0) return false;
            if (y[l] <= vec[i]) return false;
            if (vec[i] < y[l]) u[l] ++;
            if (u[l] == cur) l --;
      }
      return true;

}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
      a = A,b = B,n = T;
      for (int i = 1; i <= a; i ++) {
            x[i] = X[i - 1];
            mxw = max(x[i],mxw);
      }

      for (int j = 1; j <= b; j ++) {
            y[j] = Y[j - 1];
            mxs = max(mxs,y[j]);
      }

      for (int i = 1; i <= n; i ++) {
            w[i] = W[i - 1],s[i] = S[i - 1];
            v.pb(mk(w[i],s[i]));
            if (w[i] >= mxw && s[i] >= mxs) return -1;
      }
      sort(x + 1,x + a + 1);
      sort(y + 1,y + b + 1);
      sort(v.begin(),v.end());


      int l = 0,r = n;

      while (r - l > 1) {
            int m = (r + l) >> 1;
            if (check (m)) r = m;
            else l = m;
      }
      if (check(l)) return l;
      return r;
}

Compilation message (stderr)

robots.cpp: In function 'bool check(int)':
robots.cpp:47:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < vec.size(); i ++) {
                       ~~^~~~~~~~~~~~

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