Submission #258773

#	Time	Username	Problem	Language	Result	Execution time	Memory
258773		Kastanda	Hamburg Steak (JOI20_hamburg)	C++11	21 / 100	3093 ms	6620 KiB

hamburg

// M
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
struct Data {int a, b, c, d;};
int n, k, M[N];;
Data A[N];
mt19937 Rnd(time(0));
inline Data Merge(Data X, Data Y)
{
        Data R;
        R.a = max(X.a, Y.a);
        R.b = max(X.b, Y.b);
        R.c = min(X.c, Y.c);
        R.d = min(X.d, Y.d);
        return R;
}
inline bool OK(Data X)
{
        return (X.a <= X.c && X.b <= X.d);
}
int main()
{
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i ++)
                scanf("%d%d%d%d", &A[i].a, &A[i].b, &A[i].c, &A[i].d);
        vector < int > Priority;
        while (true)
        {
                // May God help us ...
                vector < int > P;
                memset(M, 0, sizeof(M));
                for (int i : Priority)
                        M[i] = 1, P.push_back(i);
                shuffle(P.begin(), P.end(), Rnd);

                for (int i = 1; i <= n; i ++)
                        if (!M[i]) P.push_back(i);
                shuffle(P.begin() + (int)Priority.size(), P.end(), Rnd);
                Priority.clear();

                Data F[4];
                for (int j = 0; j < k; j ++)
                        F[j].a = F[j].b = 0, F[j].c = F[j].d = 1e9 + 9;
                for (int i : P)
                {
                        bool Fail = 1;
                        for (int j = 0; j < k && Fail; j ++)
                                if (OK(Merge(A[i], F[j])))
                                        F[j] = Merge(A[i], F[j]), Fail = 0;
                        if (Fail)
                                Priority.push_back(i);
                }
                if (!Priority.size())
                {
                        for (int j = 0; j < k; j ++)
                                printf("%d %d\n", F[j].a, F[j].b);
                        return 0;
                }
        }
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |         scanf("%d%d", &n, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:26:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |                 scanf("%d%d%d%d", &A[i].a, &A[i].b, &A[i].c, &A[i].d);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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