oj.uz

Submission #226781

# Submission time Handle Problem Language Result Execution time Memory
226781 2020-04-25T10:26:04 Z MKopchev Hamburg Steak (JOI20_hamburg) C++14
2 / 100
 167 ms 6636 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 148 ms 6616 KB Output is correct
6 Correct 145 ms 6596 KB Output is correct
7 Correct 167 ms 6604 KB Output is correct
8 Correct 148 ms 6636 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -