Submission #648442

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
648442	2022-10-06T13:43:44 Z	406	Hamburg Steak (JOI20_hamburg)	C++17	Compilation error	0 ms	0 KB

hamburg

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int N = 2e5 + 50;
const int M = 2 * N + 5;
int l[N], r[N], u[N], d[N], n, k;
bitset<N> used, full;
vector<pair<int, int>> points;
vector<int> X, Y;
int cl[M], op[M], count;

void rec();

inline bool inter(int i, int x, int y) {
        return l[i] <= x && x <= r[i] && d[i] <= y && y <= u[i];
}

inline void add_point(int x, int y) {
        vector<int> change;
        for (int i = used._Find_first(); i < n; i = used._Find_next(i)) {
                if (inter(i, x, y)) {
                        count--;
                        used[i] = false;
                        change.push_back(i);
                }
        }
        if (change.empty())
                return;
        points.emplace_back(x, y);

        rec();

        for (auto cc: change) used[cc] = true, count++;
        points.pop_back();

}

void rec() {
        if (!count && points.size() <= k) {
                for (int i = 0; i < (int) points.size(); i++)
                        cout << X[points[i].first] << ' ' << Y[points[i].second] << '\n';
                for (int i = points.size(); i < k; i++)
                        cout << 1 << ' ' << 1 << '\n';
                exit(0);
        }
        if (points.size() >= k)
                return;

        int minR = 2 * n;
        int minU = 2 * n;
        int maxD = 0;
        int maxL = 0;

        for (int i = used._Find_first(); i < n; i = used._Find_next(i)) {
                minR = min(minR, r[i]);
                maxL = max(maxL, l[i]);

                minU = min(minU, u[i]);
                maxD = max(maxD, d[i]);
        }

        if (maxL <= minR || maxD <= minU) {
                add_point(minR, minU);
        }
        else {
                add_point(minR, minU);
                add_point(minR, maxD);
                add_point(maxL, minU);
                add_point(maxL, maxD);
                if (points.size())
                        return;

                int mxD = 0;
                int mnU = 2 * n;
                for (int i = 0; i < n; i++) if (l[i] <= minR) {
                        mxD = max(mxD, d[i]);
                        mnU = min(mnU, u[i]);
                }
                add_point(minR, mxD);
                add_point(minR, mnU);
                mxD = 0;
                mnU = 2 * n;
                for (int i = 0; i < n; i++) if (r[i] >= maxL) {
                        mxD = max(mxD, d[i]);
                        mnU = min(mnU, u[i]);
                }

                add_point(maxL, mxD);
                add_point(maxL, mnU);

                int mxL = 0;
                int mnR = 2 * n;

                for (int i = 0; i < n; i++) if (u[i] >= maxD) {
                        mxL = max(mxL, l[i]);
                        mnR = min(mnR, r[i]);
                }
                add_point(mxL, maxD);
                add_point(mnR, maxD);

                mxL = 0;
                mnR = 2 * n;

                for (int i = 0; i < n; i++) if (d[i] <= minU) {
                        mxL = max(mxL, l[i]);
                        mnR = min(mnR, r[i]);
                }

                add_point(mxL, minU);
                add_point(mnR, minU);

                for (int i = 0; i < n; i++) if (l[i] <= minR)
                        op[d[i]]++, cl[u[i]]++;

                vector<int> p{-2};
                for (int h = 0; h < Y.size(); h++) {
                        if (p.back() == (h - 1))
                                p.back()++;
                        else if (op[h])
                                p.push_back(h);
                        if (cl[h])
                                p.push_back(-1);
                }
                random_shuffle(p.begin(), p.end());

                for (auto h: p) if (h < 0)
                        add_point(minR, h);
        }
}

signed main() {
        ios::sync_with_stdio(0);
        cin.tie(0);

        cin >> n >> k;
        X.reserve(2 * n), Y.reserve(2 * n);
        for (int i = 0; i < n; i++) {
                cin >> l[i] >> d[i] >> r[i] >> u[i];
                X.push_back(l[i]);
                X.push_back(r[i]);
                Y.push_back(d[i]);
                Y.push_back(u[i]);
        }
        sort(X.begin(), X.end());
        X.resize(unique(X.begin(), X.end()) - X.begin());

        sort(Y.begin(), Y.end());
        Y.resize(unique(Y.begin(), Y.end()) - Y.begin());

        for (int i = 0; i < n; i++) {
                l[i] = lower_bound(X.begin(), X.end(), l[i]) - X.begin();
                r[i] = lower_bound(X.begin(), X.end(), r[i]) - X.begin();

                u[i] = lower_bound(Y.begin(), Y.end(), u[i]) - Y.begin();
                d[i] = lower_bound(Y.begin(), Y.end(), d[i]) - Y.begin();
        }

        for (int i = 0; i < n; i++)
                used[i] = true;
        count = n;

        rec();
        cout << "NO I DID NOT FIND ANYTHING\n";
        return 0;
}

Compilation message

hamburg.cpp: In function 'void add_point(int, int)':
hamburg.cpp:25:25: error: reference to 'count' is ambiguous
   25 |                         count--;
      |                         ^~~~~
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from hamburg.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:101:1: note: candidates are: 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, typename std::iterator_traits<_II>::difference_type> std::count(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&)'
  101 | count(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~~
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from hamburg.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4077:5: note:                 'template<class _IIter, class _Tp> typename std::iterator_traits< <template-parameter-1-1> >::difference_type std::count(_IIter, _IIter, const _Tp&)'
 4077 |     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
      |     ^~~~~
hamburg.cpp:13:19: note:                 'int count'
   13 | int cl[M], op[M], count;
      |                   ^~~~~
hamburg.cpp:36:48: error: reference to 'count' is ambiguous
   36 |         for (auto cc: change) used[cc] = true, count++;
      |                                                ^~~~~
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from hamburg.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:101:1: note: candidates are: 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, typename std::iterator_traits<_II>::difference_type> std::count(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&)'
  101 | count(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~~
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from hamburg.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4077:5: note:                 'template<class _IIter, class _Tp> typename std::iterator_traits< <template-parameter-1-1> >::difference_type std::count(_IIter, _IIter, const _Tp&)'
 4077 |     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
      |     ^~~~~
hamburg.cpp:13:19: note:                 'int count'
   13 | int cl[M], op[M], count;
      |                   ^~~~~
hamburg.cpp: In function 'void rec()':
hamburg.cpp:42:14: error: reference to 'count' is ambiguous
   42 |         if (!count && points.size() <= k) {
      |              ^~~~~
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from hamburg.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:101:1: note: candidates are: 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, typename std::iterator_traits<_II>::difference_type> std::count(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&)'
  101 | count(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~~
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from hamburg.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4077:5: note:                 'template<class _IIter, class _Tp> typename std::iterator_traits< <template-parameter-1-1> >::difference_type std::count(_IIter, _IIter, const _Tp&)'
 4077 |     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
      |     ^~~~~
hamburg.cpp:13:19: note:                 'int count'
   13 | int cl[M], op[M], count;
      |                   ^~~~~
hamburg.cpp:42:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |         if (!count && points.size() <= k) {
      |                       ~~~~~~~~~~~~~~^~~~
hamburg.cpp:49:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         if (points.size() >= k)
      |             ~~~~~~~~~~~~~~^~~~
hamburg.cpp:119:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |                 for (int h = 0; h < Y.size(); h++) {
      |                                 ~~^~~~~~~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:163:9: error: reference to 'count' is ambiguous
  163 |         count = n;
      |         ^~~~~
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from hamburg.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:101:1: note: candidates are: 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, typename std::iterator_traits<_II>::difference_type> std::count(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&)'
  101 | count(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~~
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from hamburg.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4077:5: note:                 'template<class _IIter, class _Tp> typename std::iterator_traits< <template-parameter-1-1> >::difference_type std::count(_IIter, _IIter, const _Tp&)'
 4077 |     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
      |     ^~~~~
hamburg.cpp:13:19: note:                 'int count'
   13 | int cl[M], op[M], count;
      |                   ^~~~~