Submission #547103

#	Time	Username	Problem	Language	Result	Execution time	Memory
547103		blue	Robots (IOI13_robots)	C++17	Compilation error	0 ms	0 KiB

robots

#include "robots.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
 
 
int A; //# weak robots
 
int B; //# small robots
 
int T; //# toys
int* W1;
int* S1;
 
struct toyW
{
    int k;
};
 
bool operator < (toyW P, toyW Q)
{
    if(W1[P.k] == W1[Q.k]) return P.k < Q.k;
    return W1[P.k] < W1[Q.k];
}
 
struct toyS
{
    int k;
};
 
bool operator < (toyS P, toyS Q)
{
    if(S1[P.k] == S1[Q.k]) return P.k < Q.k;
    return S1[P.k] < S1[Q.k];
}
set<toyW> TW_1;
set<toyW> TW1;
set<toyS> TS2;
 
// int binary_search(int a, int b, int X[], int Y[], int W[], int S[])
// {
    
// }
 
 
int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[])
{
 
    A = a;
    sort(X, X+A, [] (int u, int v)
    {
        return u < v;
    });
 
    // cerr << "check\n";
 
 
    B = b;
    sort(Y, Y+B, [] (int u, int v)
    {
        return u < v;
    });
    // cerr << "check\n";
 
 
    T = t;
    W1 = &W[0];
    S1 = &S[0];
    for(int k = 0; k < T; k++)
    {
        if((A == 0 || W[k] >= X[A-1]) && (B == 0|| S[k] >= Y[B-1]))
            return -1;
 
        TW_1.insert(toyW{k});
    }
    // cerr << "checking\n";
    // cerr << "check\n";

    int lo = 1;
    int hi = T;
    while(1)
    {
        if(lo == hi) return lo;
 
        TW1 = TW_1;
        TS2.clear();
     
        // cerr << "searching range " << a << ' ' << b << '\n';
     
        int m = (lo+hi)/2; //The maximum capacity of any robot.
     
        // for(int x: X) //weak robots
        for(int q = 0; q < A; q++) {int x = X[q];
            // cerr << "x = " << x << '\n';
            while(!TW1.empty() && W[TW1.begin()->k] < x)
            {
                int k = TW1.begin()->k;
     
                TW1.erase(toyW{k});
                TS2.insert(toyS{k});
            }
            int ctr = 0;
            while(!TS2.empty() && ctr < m)
            {
                ctr++;
                int k = TS2.rbegin()->k;
                TS2.erase(toyS{k});
            }
        }
        while(!TW1.empty())
        {
            int k = TW1.rbegin()->k;
     
            TW1.erase(toyW{k});
            TS2.insert(toyS{k});
        }
     
        for(int z = 0; z < B; z++) {int y = Y[z]; //small robots
            // cerr << "y = " << y << '\n';
            int ctr = 0;
            while(!TS2.empty() && S[TS2.begin()->k] < y && ctr < m)
            {
                ctr++;
                TS2.erase(TS2.begin());
            }
        }
     
        if(!TS2.empty())
            return binary_search(m+1, hi, X, Y, W, S);
        else
            return binary_search(lo, m, X, Y, W, S);
    }
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:131:53: error: no matching function for call to 'binary_search(int, int&, int*&, int*&, int*&, int*&)'
  131 |             return binary_search(m+1, hi, X, Y, W, S);
      |                                                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from robots.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:2262:5: note: candidate: 'template<class _FIter, class _Tp> bool std::binary_search(_FIter, _FIter, const _Tp&)'
 2262 |     binary_search(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_algo.h:2262:5: note:   template argument deduction/substitution failed:
robots.cpp:131:53: note:   candidate expects 3 arguments, 6 provided
  131 |             return binary_search(m+1, hi, X, Y, W, S);
      |                                                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from robots.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:2296:5: note: candidate: 'template<class _FIter, class _Tp, class _Compare> bool std::binary_search(_FIter, _FIter, const _Tp&, _Compare)'
 2296 |     binary_search(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_algo.h:2296:5: note:   template argument deduction/substitution failed:
robots.cpp:131:53: note:   candidate expects 4 arguments, 6 provided
  131 |             return binary_search(m+1, hi, X, Y, W, S);
      |                                                     ^
robots.cpp:133:51: error: no matching function for call to 'binary_search(int&, int&, int*&, int*&, int*&, int*&)'
  133 |             return binary_search(lo, m, X, Y, W, S);
      |                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from robots.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:2262:5: note: candidate: 'template<class _FIter, class _Tp> bool std::binary_search(_FIter, _FIter, const _Tp&)'
 2262 |     binary_search(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_algo.h:2262:5: note:   template argument deduction/substitution failed:
robots.cpp:133:51: note:   candidate expects 3 arguments, 6 provided
  133 |             return binary_search(lo, m, X, Y, W, S);
      |                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from robots.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:2296:5: note: candidate: 'template<class _FIter, class _Tp, class _Compare> bool std::binary_search(_FIter, _FIter, const _Tp&, _Compare)'
 2296 |     binary_search(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_algo.h:2296:5: note:   template argument deduction/substitution failed:
robots.cpp:133:51: note:   candidate expects 4 arguments, 6 provided
  133 |             return binary_search(lo, m, X, Y, W, S);
      |                                                   ^