Submission #226778

#	Time	Username	Problem	Language	Result	Execution time	Memory
226778		MKopchev	Hamburg Steak (JOI20_hamburg)	C++14	6 / 100	3082 ms	4412 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 order[nmax];

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);
    }

    while(1)
    {
        for(int i=1;i<=n;i++)
            order[i]=i;

        shuffle(order+1,order+n+1,rng);

        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(int i=1;i<=n;i++)
        {
            bool choose=0;
            for(int j=1;j<=k;j++)
            {
                int x1=max(inp[order[i]].x1,outp[j].x1);
                int y1=max(inp[order[i]].y1,outp[j].y1);

                int x2=min(inp[order[i]].x2,outp[j].x2);
                int y2=min(inp[order[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;
                    break;
                }
            }

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

        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:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     scanf("%i%i",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
hamburg.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |         scanf("%i%i%i%i",&inp[i].x1,&inp[i].y1,&inp[i].x2,&inp[i].y2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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