Submission #1087990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087990		MateiKing80	Robots (IOI13_robots)	C++14	Compilation error	0 ms	0 KiB

robots

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

using namespace std;

using ll = long long;
#define int ll

using pii = pair<int, int>;
#define fr first
#define sc second


struct AIB
{
    vector<int> aib;
    int n;

    inline int lsb(int x)
    {
        return x & -x;
    }

    AIB(int N, int k)
    {
        n = N;
        aib.resize(n + 1);
        for(int i = 1; i <= n; i ++)
            aib[i] = lsb(i) * k;
    }

    void upd(int pos)
    {
        while(pos <= n)
            aib[pos] --, pos += lsb(pos);
    }

    int query(int pos)
    {
        int ans = 0;
        while(pos)
        {
            ans += aib[pos];
            pos -= lsb(pos);
        }
        return ans;
    }

    int binara(int val)
    {
        int pas = (1 << 20), pos = 0, ans = 0;
        while(pas)
        {
            if(pos + pas <= n && aib[pos + pas] + ans < val)
                pos += pas, ans += aib[pos];
            pas /= 2;
        }
        return pos;
    }
};

bool doable(int a, int b, int t, vector<pii> &r)
{
    /*for(auto i : r)
        cout << i.fr << " " << i.sc << '\n';*/
    AIB ds(a, t);
    vector<pii> baga;
    for(auto i : r)
    {
        //cout << i.fr << " " << i.sc << '\n';
        baga.push_back(i);
        if(i.fr == -1)
            continue;
        int p = ds.query(i.fr + 1);
        //cout << "p: " << p << '\n';
        if(p == 0)
            continue;
        baga.pop_back();
        //cout << "chestie: " << ds.binara(p) + 1 << '\n';
        ds.upd(ds.binara(p) + 1);
    }
    /*for(auto i : baga)
        cout << i.fr << " " << i.sc << '\n';*/
    AIB ds2(b, t);
    for(auto i : baga)
    {
        if(i.sc == -1)
            return false;
        int p = ds2.query(i.sc + 1);
        if(p == 0)
            return false;
        ds2.upd(ds2.binara(p) + 1);
    }
    return true;
}

signed putaway(signed a, signed b, signed t, signed x[], signed y[], signed w[], signed s[])
{
    sort(x, x + a, greater<int>());
    sort(y, y + b, greater<int>());
    vector<pii> r;
    for(int i = 0; i < t; i ++)
    {
        int pas = (1 << 20), pos = -1;
        while(pas)
        {
            if(pos + pas < a && x[pos + pas] >= w[i])
                pos += pas;
            pas /= 2;
        }
        r.push_back({pos, 0});
        pas = (1 << 20), pos = -1;
        while(pas)
        {
            if(pos + pas < b && y[pos + pas] >= s[i])
                pos += pas;
            pas /= 2;
        }
        r.back().sc = pos;
        if(r.back() == make_pair(-1, -1))
            return -1;
    }
    sort(r.begin(), r.end(), [&](pii a, pii b){return a.sc < b.sc;});
    int pas = (1 << 20), pos = 0;
    while(pas)
    {
        if(!doable(a, b, pos + pas, r))
            pos += pas;
        //cout << "POS & PAS: " << pos << " " << pas << '\n';
        pas /= 2;
    }
    return pos + 1;
}
/*
int main()
{
    int a, b, t, x[50005], y[50005], w[50005], s[50005];
    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);
}*/
/*
3
2
10
6 2 9
4 7
4 8 2 7 1 5 3 8 7 10
6 5 3 9 8 1 3 7 6 5
*/

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:120:21: error: no match for 'operator==' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} and 'std::pair<int, int>')
  120 |         if(r.back() == make_pair(-1, -1))
      |            ~~~~~~~~ ^~ ~~~~~~~~~~~~~~~~~
      |                  |              |
      |                  |              pair<int,int>
      |                  pair<long long int,long long int>
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from robots.cpp:2:
/usr/include/c++/10/bits/regex.h:1035:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
 1035 |     operator==(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1035:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from robots.cpp:2:
/usr/include/c++/10/bits/regex.h:1131:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)'
 1131 |     operator==(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1131:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from robots.cpp:2:
/usr/include/c++/10/bits/regex.h:1206:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1206 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1206:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from robots.cpp:2:
/usr/include/c++/10/bits/regex.h:1298:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)'
 1298 |     operator==(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1298:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from robots.cpp:2:
/usr/include/c++/10/bits/regex.h:1373:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1373 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1373:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from robots.cpp:2:
/usr/include/c++/10/bits/regex.h:1466:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)'
 1466 |     operator==(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1466:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from robots.cpp:2:
/usr/include/c++/10/bits/regex.h:1545:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1545 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1545:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from robots.cpp:2:
/usr/include/c++/10/bits/regex.h:2101:5: note: candidate: 'template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator==(const std::__cxx11::match_results<_BiIter, _Alloc>&, const std::__cxx11::match_results<_BiIter, _Alloc>&)'
 2101 |     operator==(const match_results<_Bi_iter, _Alloc>& __m1,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:2101:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from robots.cpp:2:
/usr/include/c++/10/bits/postypes.h:222:5: note: candidate: 'template<class _StateT> bool std::operator==(const std::fpos<_StateT>&, const std::fpos<_StateT>&)'
  222 |     operator==(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/postypes.h:222:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::fpos<_StateT>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from robots.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:466:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator==(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
  466 |     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:466:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   deduced conflicting types for parameter '_T1' ('long long int' and 'int')
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from robots.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:360:5: note: candidate: 'template<class _Iterator> bool std::operator==(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
  360 |     operator==(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:360:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from robots.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:398:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator==(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  398 |     operator==(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:398:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from robots.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:1427:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator==(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1427 |     operator==(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1427:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::move_iterator<_IteratorL>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from robots.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:1495:5: note: candidate: 'template<class _Iterator> bool std::operator==(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
 1495 |     operator==(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1495:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::move_iterator<_IteratorL>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/string:41,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from robots.cpp:2:
/usr/include/c++/10/bits/allocator.h:206:5: note: candidate: 'template<class _T1, class _T2> bool std::operator==(const std::allocator<_CharT>&, const std::allocator<_T2>&)'
  206 |     operator==(const allocator<_T1>&, const allocator<_T2>&)
      |     ^~~~~~~~
/usr/include/c++/10/bits/allocator.h:206:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::allocator<_CharT>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from robots.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6153:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator==(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
 6153 |     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6153:5: note:   template argument deduction/substitution failed:
robots.cpp:120:40: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
  120 |         if(r.back() == make_pair(-1, -1))
      |                                        ^
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from robots.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6161:5: note: candidate: 'template<class _CharT> typename __gnu_cxx::__enable_if<std::__is_char<_Tp>::__value, bool>::__type std::operator==(const std::__cxx11::basic_string<_CharT>&, const std::__cxx11::basic_string<_CharT>&)'
 6161 |     operator==(const basic_string<_CharT>& __lhs,
      |