Submission #817122

#	Time	Username	Problem	Language	Result	Execution time	Memory
817122		gun_gan	Robots (IOI13_robots)	C++17	100 / 100	1530 ms	32612 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int inf = 1e9;

int A, B, T;
vector<int> X, Y, W, S;
vector<pair<int,int>> v, vv; // sorted by size, sorted by weight

bool can(int x) {
      if(1LL * x * A + 1LL * x * B < T) return 0;

      priority_queue<int> pq;

      int pt = 0;
      for(int i = 0; i < A; i++) {
            while(pt < vv.size() && vv[pt].first < X[i]) {
                  pq.push(S[vv[pt].second]);
                  pt++;
            }

            int c = 0;
            while(!pq.empty() && c < x) {
                  pq.pop();
                  c++;
            }
      }

      while(pt < vv.size()) {
            pq.push(S[vv[pt].second]);
            pt++;
      }

      for(int i = 0; i < B; i++) { // ambil x toys dgn size terbesar yg bisa 
            int c = 0;
            while(c < x && !pq.empty() && pq.top() < Y[i]) {
                  pq.pop();
                  c++;
            }
      }

      return pq.empty();
}

int putaway(int _A, int _B, int _T, int _X[], int _Y[], int _W[], int _S[]) {
      A = _A, B = _B, T = _T;

      for(int i = 0; i < A; i++) X.push_back(_X[i]);
      for(int i = 0; i < B; i++) Y.push_back(_Y[i]);
      for(int i = 0; i < T; i++) W.push_back(_W[i]);
      for(int i = 0; i < T; i++) S.push_back(_S[i]);

      sort(X.begin(), X.end());
      sort(Y.rbegin(), Y.rend());

      for(int i = 0; i < T; i++) {
            v.push_back({S[i], i});
            vv.push_back({W[i], i});
      }

      sort(v.begin(), v.end());
      sort(vv.begin(), vv.end());

      int l = 0, r = 1e6, res = -1;
      while(l <= r) {
            int mid = (l + r) >> 1;
            if(can(mid)) {
                  r = mid - 1, res = mid; 
            } else {
                  l = mid + 1;
            }
      }

      return res;
}

// int x[100], y[100], w[100], s[100];

// int main() {
//       cin.tie(0); ios_base::sync_with_stdio(0);

//       int A, B, T;
//       cin >> A >> B >> T;

//       for(int i = 0; i < A; i++) cin >> x[i];
//       for(int i = 0; i < B; i++) cin >> y[i];
//       for(int i = 0; i < T; i++) cin >> w[i];
//       for(int i = 0; i < T; i++) cin >> s[i];

//       cout << putaway(A, B, T, x, y, w, s) << '\n';
// }

Compilation message (stderr)

robots.cpp: In function 'bool can(int)':
robots.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |             while(pt < vv.size() && vv[pt].first < X[i]) {
      |                   ~~~^~~~~~~~~~~
robots.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |       while(pt < vv.size()) {
      |             ~~~^~~~~~~~~~~

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