Submission #816359

#	Time	Username	Problem	Language	Result	Execution time	Memory
816359		makanhulia	Robots (IOI13_robots)	C++17	100 / 100	1582 ms	20780 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;

      // set<pair<int, int>> st;

      priority_queue<int> pq;

      // cout << "x = " << x << '\n';

      int pt = 0;
      for(int i = 0; i < A; i++) {
            while(pt < vv.size() && vv[pt].first < X[i]) { // kalo weightnya oke ambil
                  // st.insert({S[vv[pt].second], vv[pt].second});
                  pq.push(S[vv[pt].second]);
                  pt++;
            }

            int c = 0;
            while(!pq.empty() && c < x) {
                  // cout << "apus " << st.rbegin()->first << " " << st.rbegin()->second << '\n';
                  // st.erase(*st.rbegin());
                  pq.pop();
                  c++;
            }

            // cout << i << " " << st.size() << " " << pt << '\n';
      }

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

      // cout << st.size() << '\n';

      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();
                  // auto it = st.lower_bound(make_pair(Y[i], -inf)); // liat sizenya
                  // if(it != st.begin()) {
                  //       it--;
                  //       st.erase(it);
                  // } else {
                  //       break;
                  // }
                  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());

      // for(auto [w, j] : vv) {
      //       cout << w << " " << j << '\n';
      // }
      // cout << '\n';
      // cout << can(2) << '\n';

      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:23: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]
   23 |             while(pt < vv.size() && vv[pt].first < X[i]) { // kalo weightnya oke ambil
      |                   ~~~^~~~~~~~~~~
robots.cpp:40: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]
   40 |       while(pt < vv.size()) {
      |             ~~~^~~~~~~~~~~

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