Submission #217161

#	Time	Username	Problem	Language	Result	Execution time	Memory
217161		rama_pang	Hamburg Steak (JOI20_hamburg)	C++14	21 / 100	3082 ms	5888 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, K;
  cin >> N >> K;

  vector<int> L(N), D(N), R(N), U(N);
  for (int i = 0; i < N; i++) {
    cin >> L[i] >> D[i] >> R[i] >> U[i];
  }
  
  vector<int> ids(N);
  iota(begin(ids), end(ids), 0);

  vector<int> cannot;
  vector<int> can;

  vector<array<int, 4>> ans;

  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

  while (true) {
    ans.clear();
    for (int i = 0; i < K; i++) {
      ans.push_back({1, 1, (int) 1e9, (int) 1e9});
    }

    for (auto &i : ids) {
      bool ok = false;
      for (int j = 0; j < K; j++) {
        int l = max(L[i], ans[j][0]);
        int d = max(D[i], ans[j][1]);
        int r = min(R[i], ans[j][2]);
        int u = min(U[i], ans[j][3]);
        if (l <= r && d <= u) {
          ans[j] = {l, d, r, u};
          ok = true;
          break;
        }
      }
      if (!ok) {
        cannot.emplace_back(i);
      } else {
        can.emplace_back(i);
      }
    }

    if (cannot.empty()) {
      for (int i = 0; i < K; i++) {
        cout << ans[i][0] << " " << ans[i][1] << "\n";
      }
      return 0;
    }

    shuffle(begin(cannot), end(cannot), rnd);

    ids.clear();
    for (auto &i : cannot) ids.emplace_back(i);
    for (auto &i : can) ids.emplace_back(i);

    can.clear(), cannot.clear();

  }

}

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79