oj.uz

Submission #216406

# Submission time Handle Problem Language Result Execution time Memory
216406 2020-03-27T09:16:47 Z PeppaPig Hamburg Steak (JOI20_hamburg) C++14
2 / 100
 154 ms 4604 KB 
#include <bits/stdc++.h>

using namespace std;

struct Rectangle {
    int x1, y1, x2, y2;
    Rectangle() : x1(1), y1(1), x2(1e9), y2(1e9) {}
    Rectangle(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
    friend Rectangle operator+(const Rectangle &a, Rectangle &b) {
        Rectangle ret;
        ret.x1 = max(a.x1, b.x1), ret.y1 = max(a.y1, b.y1);
        ret.x2 = min(a.x2, b.x2), ret.y2 = min(a.y2, b.y2);
        return ret;
    }
};

const int N = 2e5+5;

int n, k;
vector<Rectangle> rect;
bitset<N> chk;
default_random_engine rng(time(NULL));

int main() {
    scanf("%d %d", &n, &k);
    for(int i = 1, x1, y1, x2, y2; i <= n; i++) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        rect.emplace_back(x1, y1, x2, y2);
    }
    while(true) {
        chk.reset();
        vector<Rectangle> vec(k);
        for(int i = 0; i < k; i++) for(int j = 0; j < n; j++) {
            if(chk[j]) continue;
            Rectangle now = vec[i] + rect[j];
            if(now.x1 <= now.x2 && now.y1 <= now.y2)
                chk[j] = 1, vec[i] = now;
        } 
        if(chk.count() == n) {
            for(int i = 0; i < k; i++) printf("%d %d\n", vec[i].x1, vec[i].y1);
            return 0;
        }
        vector<int> perm(n);
        vector<Rectangle> nex;
        for(int i = 0; i < n; i++) perm.emplace_back(i);
        shuffle(perm.begin(), perm.end(), rng);
        for(int i = 0; i < n; i++) if(!chk[perm[i]]) 
            nex.emplace_back(rect[perm[i]]); 
        for(int i = 0; i < n; i++) if(chk[perm[i]]) 
            nex.emplace_back(rect[perm[i]]);
        swap(rect, nex);
    }

    return 0;
}

Compilation message

hamburg.cpp: In function 'int main()':
hamburg.cpp:39:24: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |         if(chk.count() == n) {
      |            ~~~~~~~~~~~~^~~~
hamburg.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |         scanf("%d %d %d %d", &x1, &y1, &x2, &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
0 / 1.0

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

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 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 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 154 ms 4604 KB Output is correct
6 Correct 147 ms 4580 KB Output is correct
7 Correct 141 ms 4584 KB Output is correct
8 Correct 140 ms 4580 KB Output is correct

Subtask #6
0 / 3.0

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

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 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 -