Submission #956041

#	Time	Username	Problem	Language	Result	Execution time	Memory
956041		ZeroCool	Robots (IOI13_robots)	C++14	14 / 100	1300 ms	30056 KiB

robots

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

using namespace std;

const int N = 1e6 + 10;
const int M = 1e5 + 10;

#define pb push_back

int n,a,b;

int _W[N], _S[N];
int _X[N];
int _Y[N];

pair<int,int> _A[N];

bool ok(int mid){
    int p = 0;
    priority_queue<int> pq;

    for(int i = 0;i<a;i++){
        while(p < n && _A[p].first < _X[i]){
            pq.push(_A[p].second);
            p++;
        }
        int k = mid;
        while(pq.size() && k--){
            pq.pop();
        }
    }

    while(p < n)pq.push(_A[p++].second);
    vector<int> v;
    while(pq.size()){
        v.pb(pq.top());
        pq.pop();
    }

    for(int i =0 ;i<b;i++){
        int k = mid;
        while(v.size() && v.back() < _Y[i] && k--){
            v.pop_back();
        }
    }
    return v.empty();
}

int putaway(int A, int B, int T, int x[], int y[], int w[], int s[]) {
    a = A;
    b = B;
    n = T;
    sort(x, x+a);
    sort(y, y + b);
    memcpy(_X, x, sizeof x);
    memcpy(_Y, y, sizeof y);
    
    for(int i = 0;i<n;i++){
        _A[i] = {w[i], s[i]};
    }
    sort(_A, _A+n);

    int lo = 1;
    int hi = n;
  //  int ans = -1;
    while(lo <= hi){
        int mid = (lo + hi) / 2;

        if(ok(mid)){
            hi = mid -1;
           // ans = mid;

        }else lo = mid + 1;
    }
    if(hi == T)return -1;
    return hi + 1;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:56:26: warning: 'sizeof' on array function parameter 'x' will return size of 'int*' [-Wsizeof-array-argument]
   56 |     memcpy(_X, x, sizeof x);
      |                          ^
robots.cpp:50:38: note: declared here
   50 | int putaway(int A, int B, int T, int x[], int y[], int w[], int s[]) {
      |                                  ~~~~^~~
robots.cpp:56:19: warning: argument to 'sizeof' in 'void* memcpy(void*, const void*, size_t)' call is the same expression as the source; did you mean to dereference it? [-Wsizeof-pointer-memaccess]
   56 |     memcpy(_X, x, sizeof x);
      |                   ^~~~~~~~
robots.cpp:57:26: warning: 'sizeof' on array function parameter 'y' will return size of 'int*' [-Wsizeof-array-argument]
   57 |     memcpy(_Y, y, sizeof y);
      |                          ^
robots.cpp:50:47: note: declared here
   50 | int putaway(int A, int B, int T, int x[], int y[], int w[], int s[]) {
      |                                           ~~~~^~~
robots.cpp:57:19: warning: argument to 'sizeof' in 'void* memcpy(void*, const void*, size_t)' call is the same expression as the source; did you mean to dereference it? [-Wsizeof-pointer-memaccess]
   57 |     memcpy(_Y, y, sizeof y);
      |                   ^~~~~~~~

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