Submission #231550

#	Time	Username	Problem	Language	Result	Execution time	Memory
231550		duality	Hamburg Steak (JOI20_hamburg)	C++11	21 / 100	3075 ms	7768 KiB

hamburg

#define DEBUG 0

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

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

int L[200000],D[200000],R[200000],U[200000];
vi xLines,yLines;
int order[200000];
struct rect { int l,d,r,u; };
vector<rect> ans;
int main() {
    int i;
    int N,K;
    scanf("%d %d",&N,&K);
    for (i = 0; i < N; i++) {
        scanf("%d %d %d %d",&L[i],&D[i],&R[i],&U[i]);
        xLines.pb(L[i]),xLines.pb(R[i]+1);
        yLines.pb(D[i]),yLines.pb(U[i]+1);
    }
    sort(xLines.begin(),xLines.end());
    xLines.resize(unique(xLines.begin(),xLines.end())-xLines.begin());
    sort(yLines.begin(),yLines.end());
    yLines.resize(unique(yLines.begin(),yLines.end())-yLines.begin());
    for (i = 0; i < N; i++) {
        L[i] = lower_bound(xLines.begin(),xLines.end(),L[i])-xLines.begin();
        D[i] = lower_bound(yLines.begin(),yLines.end(),D[i])-yLines.begin();
        R[i] = lower_bound(xLines.begin(),xLines.end(),R[i]+1)-xLines.begin()-1;
        U[i] = lower_bound(yLines.begin(),yLines.end(),U[i]+1)-yLines.begin()-1;
    }

    int j;
    for (i = 0; i < N; i++) order[i] = i;
    while (1) {
        random_shuffle(order,order+N);
        for (i = 0; i < N; i++) {
            int u = order[i],b = -1,bb = 0;
            for (j = 0; j < ans.size(); j++) {
                if ((L[u] > ans[j].r) || (R[u] < ans[j].l) || (D[u] > ans[j].u) || (U[u] < ans[j].d)) continue;
                else {
                    rect x = ans[j];
                    x.l = max(x.l,L[u]);
                    x.d = max(x.d,D[u]);
                    x.r = min(x.r,R[u]);
                    x.u = min(x.u,U[u]);
                    if ((b == -1) || (ans[j].u-ans[j].d+ans[j].r-ans[j].l-(x.u-x.d+x.r-x.l) < bb)) {
                        b = j;
                        bb = ans[j].u-ans[j].d+ans[j].r-ans[j].l-(x.u-x.d+x.r-x.l);
                    }
                }
            }
            if (b == -1) ans.pb((rect){L[u],D[u],R[u],U[u]});
            else {
                rect x = ans[b];
                x.l = max(x.l,L[u]);
                x.d = max(x.d,D[u]);
                x.r = min(x.r,R[u]);
                x.u = min(x.u,U[u]);
                ans[b] = x;
            }
            if (ans.size() > K) break;
        }
        if (i == N) {
            for (j = 0; j < K; j++) {
                if (j < ans.size()) printf("%d %d\n",xLines[ans[j].l],yLines[ans[j].d]);
                else printf("0 0\n");
            }
            return 0;
        }
        else ans.clear();
    }

    return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for (j = 0; j < ans.size(); j++) {
      |                         ~~^~~~~~~~~~~~
hamburg.cpp:112:28: warning: comparison of integer expressions of different signedness: 'std::vector<rect>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |             if (ans.size() > K) break;
      |                 ~~~~~~~~~~~^~~
hamburg.cpp:116:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |                 if (j < ans.size()) printf("%d %d\n",xLines[ans[j].l],yLines[ans[j].d]);
      |                     ~~^~~~~~~~~~~~
hamburg.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d %d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~
hamburg.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |         scanf("%d %d %d %d",&L[i],&D[i],&R[i],&U[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79