oj.uz

Submission #213396

# Submission time Handle Problem Language Result Execution time Memory
213396 2020-03-25T17:12:29 Z popovicirobert Hamburg Steak (JOI20_hamburg) C++14
6 / 100
 3000 ms 3576 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int


using namespace std;

const int INF = (int) 2e9;

struct Rect {
	int x1, y1, x2, y2;
	Rect(int _x1 = -INF, int _y1 = -INF, int _x2 = INF, int _y2 = INF) : x1(_x1), y1(_y1), x2(_x2), y2(_y2) {}
	bool ok() {
		return x1 <= x2 && y1 <= y2;
	}
};

inline Rect inter(Rect a, Rect b) {
	return Rect(max(a.x1, b.x1), max(a.y1, b.y1), min(a.x2, b.x2), min(a.y2, b.y2));
}

int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, n, k;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;
    vector<Rect> r(n);
    for(i = 0; i < n; i++) {
    	cin >> r[i].x1 >> r[i].y1 >> r[i].x2 >> r[i].y2;
    }

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    while(true) {
    	shuffle(r.begin(), r.end(), rng);
    	vector<pair<int, int>> sol;
    	vector<bool> vis(n);
    	for(int j = 0; j < k; j++) {
    		Rect cur;
    		for(i = 0; i < n; i++) {
    			if(vis[i] == 0) {
    				if(inter(cur, r[i]).ok()) {
    					cur = inter(cur, r[i]);
    					vis[i] = 1;
    				}
    			}
    		}
    		sol.push_back({cur.x1, cur.y1});
    	}
    	if(count(vis.begin(), vis.end(), 1) == n) {
    		int sz = (int)sol.size();
    		for(i = 0; i < k; i++) {
    			cout << sol[i % sz].first << " " << sol[i % sz].second << "\n";
    		}
    		return 0;
    	}
    }

    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 384 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 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 10 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 9 ms 416 KB Output is correct
9 Correct 46 ms 384 KB Output is correct
10 Correct 201 ms 420 KB Output is correct
11 Correct 46 ms 420 KB Output is correct
12 Correct 31 ms 384 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 384 KB Output is correct
5 Correct 15 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 617 ms 416 KB Output is correct
8 Correct 187 ms 384 KB Output is correct
9 Correct 136 ms 384 KB Output is correct
10 Correct 503 ms 384 KB Output is correct
11 Correct 245 ms 416 KB Output is correct
12 Correct 11 ms 384 KB Output is correct
13 Execution timed out 3083 ms 384 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 384 KB Output is correct
5 Correct 106 ms 3456 KB Output is correct
6 Correct 185 ms 3456 KB Output is correct
7 Correct 110 ms 3456 KB Output is correct
8 Correct 126 ms 3576 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 384 KB Output is correct
5 Execution timed out 3074 ms 3532 KB Time limit exceeded
6 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 10 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 9 ms 416 KB Output is correct
9 Correct 46 ms 384 KB Output is correct
10 Correct 201 ms 420 KB Output is correct
11 Correct 46 ms 420 KB Output is correct
12 Correct 31 ms 384 KB Output is correct
13 Execution timed out 3088 ms 3524 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 384 KB Output is correct
5 Correct 15 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 617 ms 416 KB Output is correct
8 Correct 187 ms 384 KB Output is correct
9 Correct 136 ms 384 KB Output is correct
10 Correct 503 ms 384 KB Output is correct
11 Correct 245 ms 416 KB Output is correct
12 Correct 11 ms 384 KB Output is correct
13 Execution timed out 3083 ms 384 KB Time limit exceeded
14 Halted 0 ms 0 KB -