Submission #226781

#	Time	Username	Problem	Language	Result	Execution time	Memory
226781		MKopchev	Hamburg Steak (JOI20_hamburg)	C++14	2 / 100	167 ms	6636 KiB

hamburg

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;

struct rect
{
    int x1,y1,x2,y2;
};

int n,k;

rect inp[nmax];

rect outp[nmax];

mt19937 rng(42);

int main()
{
    scanf("%i%i",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%i%i%i%i",&inp[i].x1,&inp[i].y1,&inp[i].x2,&inp[i].y2);
    }

    vector<int> correct={},wrong={};
    for(int i=1;i<=n;i++)wrong.push_back(i);

    while(1)
    {
        vector<int> order={};

        shuffle(wrong.begin(),wrong.end(),rng);

        for(auto p:wrong)order.push_back(p);
        for(auto p:correct)order.push_back(p);

        wrong={};
        correct={};

        //for(auto w:order)cout<<w<<" ";cout<<endl;

        for(int i=1;i<=k;i++)
        {
            outp[i].x1=1;
            outp[i].y1=1;
            outp[i].x2=1e9;
            outp[i].y2=1e9;
        }

        bool ok=1;

        for(auto i:order)
        {
            if(ok==0){wrong.push_back(i);continue;}

            bool choose=0;
            for(int j=1;j<=k;j++)
            {
                int x1=max(inp[i].x1,outp[j].x1);
                int y1=max(inp[i].y1,outp[j].y1);

                int x2=min(inp[i].x2,outp[j].x2);
                int y2=min(inp[i].y2,outp[j].y2);

                if(x1<=x2&&y1<=y2)
                {
                    choose=1;
                    outp[j].x1=x1;
                    outp[j].y1=y1;
                    outp[j].x2=x2;
                    outp[j].y2=y2;

                    correct.push_back(i);

                    break;
                }
            }

            if(choose==0){ok=0;}
        }

        if(ok)
        {
            for(int j=1;j<=k;j++)
                printf("%i %i\n",outp[j].x1,outp[j].y1);
            return 0;
        }
    }
    return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |     scanf("%i%i",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
hamburg.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |         scanf("%i%i%i%i",&inp[i].x1,&inp[i].y1,&inp[i].x2,&inp[i].y2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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