oj.uz

Submission #226785

# Submission time Handle Problem Language Result Execution time Memory
226785 2020-04-25T10:28:17 Z MKopchev Hamburg Steak (JOI20_hamburg) C++14
6 / 100
 3000 ms 7432 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){wrong.push_back(i);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 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 18 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 14 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 586 ms 384 KB Output is correct
8 Correct 66 ms 384 KB Output is correct
9 Correct 79 ms 384 KB Output is correct
10 Correct 69 ms 384 KB Output is correct
11 Execution timed out 3029 ms 508 KB Time limit exceeded
12 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 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 157 ms 6572 KB Output is correct
6 Correct 155 ms 6508 KB Output is correct
7 Correct 153 ms 6764 KB Output is correct
8 Correct 157 ms 6508 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1074 ms 7432 KB Output is correct
6 Execution timed out 3043 ms 6192 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 18 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 14 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 1823 ms 6984 KB Output is correct
14 Correct 927 ms 7384 KB Output is correct
15 Correct 1928 ms 7152 KB Output is correct
16 Correct 414 ms 6928 KB Output is correct
17 Correct 1233 ms 7400 KB Output is correct
18 Execution timed out 3084 ms 6548 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 586 ms 384 KB Output is correct
8 Correct 66 ms 384 KB Output is correct
9 Correct 79 ms 384 KB Output is correct
10 Correct 69 ms 384 KB Output is correct
11 Execution timed out 3029 ms 508 KB Time limit exceeded
12 Halted 0 ms 0 KB -