Submission #216406

#	Time	Username	Problem	Language	Result	Execution time	Memory
216406		PeppaPig	Hamburg Steak (JOI20_hamburg)	C++14	2 / 100	154 ms	4604 KiB

hamburg

#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 (stderr)

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 / 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