QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#317871#5378. 匹配问题yllcm0 0ms7620kbC++141.8kb2024-01-29 20:57:282024-01-29 20:57:29

Judging History

你现在查看的是最新测评结果

  • [2024-01-29 20:57:29]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:7620kb
  • [2024-01-29 20:57:28]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = 0;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 1e6 + 10;
const int INF = 1e9;
int n, la, lb;
int a[N], b[N], cnt[N], mn[N], lim[N];
int main() { 
  n = read(); la = read(); lb = read();
  for(int i = 1; i <= n; i++)a[i] = read();
  for(int i = 1; i <= n; i++)b[i] = read(), cnt[b[i]]++;
  for(int i = 1; i < N; i++)cnt[i] += cnt[i - 1];
  sort(a + 1, a + 1 + n);
  sort(b + 1, b + 1 + n);
  for(int i = 1; i <= n; i++)printf("%d ", a[i]); putchar('\n');
  for(int i = 1; i <= n; i++)printf("%d ", b[i]); putchar('\n');
  for(int i = 1; i <= n; i++) {
    int sum = 0; mn[i] = INF;
    for(int j = i; j; j--) {
      if(a[j] + la <= a[i] + lb) {
        sum++;
        mn[i] = min(mn[i], (cnt[a[i] + lb] - cnt[a[j] - 1]) - sum);
      }
    }
  }
  for(int i = 1; i <= n; i++)lim[i] = INF;
  multiset<int> s;
  int ans = 0;
  for(int i = n, j = n; i; i--) {
    while(b[j] >= a[i])s.insert(b[j--]);
    for(int j = 1; j <= i; j++) {
      if(a[j] + la > a[i] + lb) {
        lim[j] = min(lim[j], mn[i]);
        break;
      }
    }
    int flg = 1;
    for(int j = 1; j <= i; j++)if(!lim[j])flg = 0;
    if(flg) {
      auto it = s.upper_bound(a[i] + lb);
      if(it != s.begin()) {
        // printf("%d %d\n", a[i], *prev(it)); 
        ans++, s.erase(--it);
        for(int j = i; j; j--)lim[j]--;
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7620kb

input:

2 2 1
1 1
1 1

output:

1 1 
1 1 
2

result:

wrong answer 1st lines differ - expected: '2', found: '1 1 '

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #100:

score: 0
Time Limit Exceeded

input:

500000 500000 10
200184 74991 71203 334998 316800 34483 120570 301054 331108 232072 189788 397143 490296 56807 361700 88818 42376 460305 371750 450351 338384 429789 426045 445029 152316 408919 188124 144966 457495 475025 225370 260510 383159 495247 54319 246245 240728 372033 439599 119720 449020 451...

output:

1 1 2 3 5 8 10 10 11 12 12 13 14 16 17 17 18 19 20 22 24 25 25 26 26 30 31 31 33 33 35 36 37 37 38 39 39 41 41 42 42 43 43 44 44 45 46 46 47 49 51 52 54 54 54 54 55 55 55 55 56 56 59 59 62 62 63 63 64 65 66 66 67 67 68 68 70 71 72 74 76 77 77 81 82 83 84 84 85 86 87 87 89 89 91 91 94 94 96 96 99 103...

result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%