Submission #230718

#	Time	Username	Problem	Language	Result	Execution time	Memory
230718		Nightlight	Hamburg Steak (JOI20_hamburg)	C++14	21 / 100	3058 ms	5284 KiB

hamburg

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

int N, K;
int L[200005], R[200005], D[200005], U[200005];
int A[200005], ok[200005], wa[200005];
int ans[5][5];

int main() {
  scanf("%d %d", &N, &K);
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  for(int i = 1; i <= N; i++) {
    scanf("%d %d %d %d", &L[i], &D[i], &R[i], &U[i]);
    A[i] = i;
  }
  int l, r, u, d, now, p1, p2, tp;
  while(1) {
    p1 = 0, p2 = 0;
    for(int i = 1; i <= K; i++) {
      ans[i][1] = 1, ans[i][2] = 1;
      ans[i][3] = 1000000000, ans[i][4] = 1000000000;
    }
    for(int i = 1; i <= N; i++) {
      now = A[i];
      for(tp = 1; tp <= K; tp++) {
        l = max(L[now], ans[tp][1]);
        d = max(D[now], ans[tp][2]);
        r = min(R[now], ans[tp][3]);
        u = min(U[now], ans[tp][4]);
        if(l <= r && d <= u) {
          ans[tp][1] = l;
          ans[tp][2] = d;
          ans[tp][3] = r;
          ans[tp][4] = u;
          break;
        }
      }
      if(tp <= K) {
        ok[++p1] = now;
      }else {
        wa[++p2] = now;
      }
    }
    if(p2 == 0) {
      for(int i = 1; i <= K; i++) {
        printf("%d %d\n", ans[i][1], ans[i][2]);
      }
      return 0;
    }

    shuffle(wa + 1, wa + p2 + 1, rnd);
    int it = p2;
    for(int i = 1; i <= p2; i++) {
      A[i] = wa[i];
    }
    for(int i = 1; i <= p1; i++) {
      A[++it] = ok[i];
    }
  }
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:10:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |   scanf("%d %d", &N, &K);
      |   ~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |     scanf("%d %d %d %d", &L[i], &D[i], &R[i], &U[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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