QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#179022 | #5378. 匹配问题 | Lynkcat# | 18 | 16ms | 96032kb | C++20 | 2.2kb | 2023-09-14 16:44:08 | 2024-07-04 01:59:58 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
#define N 1000005
#define M 1000005
using namespace std;
int n,la,lb;
int a[N],b[N],dp[N],_n;
struct edge
{
int fm,to,val,cost,nxt;
edge(int o=0,int a=0,int b=0,int c=0,int d=0)
{
fm=o,to=a,val=b,cost=c,nxt=d;
}
}E[M<<1];
int cnt=1;
int hd[N],dis[N],cur[N],lst[N];
int S,T,ans;
int MC,MF;
int flw[N],ins[N];
void add(int x,int y,int w,int cost)
{
E[++cnt].to=y;
E[cnt].fm=x;
E[cnt].val=w;
E[cnt].nxt=hd[x];
E[cnt].cost=cost;
hd[x]=cnt;
E[++cnt].to=x;
E[cnt].fm=y;
E[cnt].val=0;
E[cnt].nxt=hd[y];
E[cnt].cost=-cost;
hd[y]=cnt;
}
bool spfa()
{
queue<int>q;
for (int i=1;i<=_n;i++) dis[i]=inf,ins[i]=0,flw[i]=0;
dis[S]=0;
q.push(S);
ins[S]=1;
flw[S]=inf;
while (!q.empty())
{
int u=q.front();q.pop();
ins[u]=0;
for (int i=hd[u];i;i=E[i].nxt)
if (E[i].val&&dis[E[i].to]>dis[u]+E[i].cost)
{
dis[E[i].to]=dis[u]+E[i].cost;
flw[E[i].to]=min(flw[u],E[i].val);
lst[E[i].to]=i;
if (!ins[E[i].to]) ins[E[i].to]=1,q.push(E[i].to);
}
}
if (dis[T]==inf) return 0;
MF+=flw[T];
MC+=dis[T]*flw[T];
int nw=T;
while (nw!=S)
{
E[lst[nw]].val-=flw[T];
E[lst[nw]^1].val+=flw[T];
nw=E[lst[nw]].fm;
}
return 1;
}
void BellaKira()
{
cin>>n>>la>>lb;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<=n;i++)
cin>>b[i];
sort(a+1,a+n+1);
sort(b+1,b+n+1);
_n=2*n+2;
S=2*n+1,T=2*n+2;
for (int i=1;i<=n;i++)
add(S,i,1,0),add(i+n,T,1,0);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (b[j]>=a[i]&&b[j]<=a[i]+la)
add(i,j+n,1,-(b[j]<=a[i]+lb));
while (spfa());
cout<<-MC<<'\n';
}
signed main()
{
// freopen("match.in","r",stdin);
// freopen("match.out","w",stdout);
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 4
Accepted
Test #1:
score: 4
Accepted
time: 4ms
memory: 93740kb
input:
2 2 1 1 1 1 1
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 8ms
memory: 93780kb
input:
10 200000 100000 34181 300096 24293 22680 402306 193269 438170 254676 188147 73971 216849 477743 461911 135785 467234 278230 287107 223666 124173 135091
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 8ms
memory: 93988kb
input:
10 200000 50000 298370 136488 436143 52173 206095 140981 321188 407844 342157 193338 138374 383207 156748 442404 386749 492604 354156 229996 447123 418264
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 4ms
memory: 93756kb
input:
10 50000 30000 306273 53088 405351 218373 335275 277816 451436 105244 418031 83336 489843 323727 219514 102964 141689 337190 131790 312365 431836 413688
output:
5
result:
ok single line: '5'
Test #5:
score: 0
Accepted
time: 13ms
memory: 93980kb
input:
10 80000 60000 224299 63826 419731 459681 408367 139676 239118 115180 368327 179613 289195 106688 418781 143169 441337 255686 228353 373168 489321 173199
output:
10
result:
ok single line: '10'
Test #6:
score: 0
Accepted
time: 13ms
memory: 93940kb
input:
10 150000 80000 218617 21495 443909 77126 349241 169574 387539 106419 251533 138042 427196 237082 192262 56014 357102 109789 495939 197573 273744 498979
output:
7
result:
ok single line: '7'
Test #7:
score: 0
Accepted
time: 0ms
memory: 93692kb
input:
10 5 1 1 28 22 4 16 13 7 10 19 25 6 9 27 12 30 24 18 15 3 21
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 7ms
memory: 93688kb
input:
10 2 1 19 13 16 22 28 25 7 1 4 10 6 21 30 9 15 12 27 18 3 24
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 8ms
memory: 93940kb
input:
9 5 1 9 1 12 2 16 5 8 15 19 18 20 4 7 14 6 21 13 11
output:
3
result:
ok single line: '3'
Test #10:
score: 0
Accepted
time: 14ms
memory: 93632kb
input:
10 500000 1 13 1 16 4 22 7 10 28 25 19 9 3 30 18 24 15 6 20 27 12
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 0ms
memory: 93632kb
input:
3 2 1 1 2 3 3 4 5
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 3ms
memory: 93908kb
input:
10 500000 499999 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282
output:
10
result:
ok single line: '10'
Subtask #2:
score: 14
Accepted
Dependency #1:
100%
Accepted
Test #13:
score: 14
Accepted
time: 8ms
memory: 93692kb
input:
100 200000 50000 216198 375994 364079 318600 289827 26059 302540 179976 362307 239456 310052 149745 283732 189278 465297 19986 492322 62889 399607 354136 103590 327594 335929 428453 474630 362205 113883 219196 488463 150086 144585 8342 98764 454065 282581 397786 274728 271563 326538 246226 384730 25...
output:
63
result:
ok single line: '63'
Test #14:
score: 0
Accepted
time: 3ms
memory: 93788kb
input:
100 200000 10000 480821 383273 197373 419379 37439 203333 299170 472531 243830 178320 365484 188981 414062 72193 411592 424204 340704 77915 241035 418858 18916 22153 349730 52029 216408 254012 239845 340707 326325 217780 49620 457023 424881 447611 180529 299451 97390 388124 62096 217848 229883 36748...
output:
50
result:
ok single line: '50'
Test #15:
score: 0
Accepted
time: 3ms
memory: 93756kb
input:
100 200000 5000 248114 369741 180383 287869 440522 23446 77242 341565 270689 231933 318395 106083 425489 353655 339921 86901 464488 473163 90027 262555 343418 64735 38062 128873 201978 157259 398800 244502 277724 193275 415958 252223 338307 425455 385803 408262 493113 470196 456942 87927 48611 13535...
output:
48
result:
ok single line: '48'
Test #16:
score: 0
Accepted
time: 3ms
memory: 93692kb
input:
100 100000 50000 486345 297886 26025 474314 100979 481518 11500 283550 332460 445057 17533 144840 221191 392737 115392 302986 454624 423360 16963 446798 30332 270733 1813 396977 352733 134622 233480 413553 229390 162339 373438 159455 456285 111216 188711 265590 452306 73 124816 278925 143310 283361 ...
output:
82
result:
ok single line: '82'
Test #17:
score: 0
Accepted
time: 0ms
memory: 93640kb
input:
100 100000 5000 439157 15849 342210 416475 203400 331705 267562 496741 5582 1527 80269 362890 93819 325171 471805 492364 426232 179298 212402 373335 320351 280366 363315 268413 180120 228943 308449 335872 155669 7017 449849 234951 12715 258464 24847 476960 498347 331138 484617 468028 15269 307198 34...
output:
43
result:
ok single line: '43'
Test #18:
score: 0
Accepted
time: 7ms
memory: 93732kb
input:
100 50000 5000 356138 75991 429667 167698 190384 320685 49056 231155 493359 58606 294380 305694 417163 211543 183439 211048 241022 110826 325734 464543 194473 243735 16536 155717 338096 404192 189355 169201 133506 495056 164315 116861 112397 262901 303833 236119 52989 331273 270007 359116 2070 25260...
output:
41
result:
ok single line: '41'
Test #19:
score: 0
Accepted
time: 4ms
memory: 93992kb
input:
100 50000 7000 278750 385984 434621 58472 322689 269436 245170 17244 456888 11920 210805 31811 289511 463364 155357 467516 459079 191267 396040 454082 460194 103191 92335 494144 114187 326720 309988 123829 214131 141758 455879 416627 2031 134103 431343 325594 81548 358209 273302 421176 259867 446631...
output:
46
result:
ok single line: '46'
Test #20:
score: 0
Accepted
time: 4ms
memory: 95736kb
input:
100 50000 10000 44671 199153 486351 64506 331287 386915 95122 54209 376550 139713 371612 188414 388792 75322 179157 370318 183962 317192 183394 351017 304929 390544 253896 334074 275884 159986 348155 8929 192946 258068 419481 63725 327275 244648 58851 289296 385871 201431 40630 255845 261638 230397 ...
output:
40
result:
ok single line: '40'
Test #21:
score: 0
Accepted
time: 7ms
memory: 96032kb
input:
100 30000 5000 370274 110702 441251 272581 129801 352167 122734 60816 261473 2126 292718 151986 8139 321067 83913 278084 103390 203161 32695 280737 164143 431372 197003 71699 61831 174258 38384 56872 419945 197154 204290 148171 337649 346984 294808 178731 381524 299625 285955 237110 425019 130281 24...
output:
36
result:
ok single line: '36'
Test #22:
score: 0
Accepted
time: 7ms
memory: 93732kb
input:
100 30000 8000 251366 436756 233765 308050 194657 435426 433129 386977 140841 136428 356400 496170 57335 389627 375625 184631 255361 454672 119519 334233 383164 157349 100449 15554 66998 57625 234164 79397 327508 375708 319035 322094 266219 56301 245907 52931 256785 32213 367928 157824 467045 49924 ...
output:
49
result:
ok single line: '49'
Test #23:
score: 0
Accepted
time: 11ms
memory: 93704kb
input:
100 20000 10000 214869 191290 19116 251609 491675 223459 457066 63933 189882 450667 343040 67504 433800 357884 11077 254264 429652 49101 262977 349432 333510 236391 383768 216721 363804 214450 456066 61650 170593 294394 37815 62425 405074 488694 194382 476654 123487 152483 247976 339464 430823 10631...
output:
65
result:
ok single line: '65'
Test #24:
score: 0
Accepted
time: 11ms
memory: 93756kb
input:
100 20000 5000 437462 329536 281051 49656 311386 383880 414050 304141 222086 464737 473489 111375 486227 33389 425895 173908 13428 333673 416322 248683 193081 170119 7585 258089 30268 462767 229201 424598 229857 498012 391803 83729 496967 399202 254599 55990 344248 65292 466212 268316 439263 329296 ...
output:
35
result:
ok single line: '35'
Test #25:
score: 0
Accepted
time: 3ms
memory: 93692kb
input:
100 20000 8000 186991 153145 224998 168406 333689 14632 43352 351492 312667 7271 450525 115816 251856 477325 64515 195920 60688 271020 155268 30582 63814 316250 14753 299856 424233 33441 328071 95459 447508 188164 355273 77339 155202 373087 447826 215904 212918 277562 304754 31015 4340 350427 250433...
output:
52
result:
ok single line: '52'
Test #26:
score: 0
Accepted
time: 3ms
memory: 95688kb
input:
100 20000 15000 44059 345504 396488 324911 213580 103158 409930 350640 488727 232174 193116 195392 481090 498251 410616 438595 455380 289496 327872 112377 139575 216353 343918 272424 127610 59561 247654 479113 123751 28485 333387 158487 420901 114134 490297 130126 23097 287176 146717 282195 283608 1...
output:
88
result:
ok single line: '88'
Test #27:
score: 0
Accepted
time: 0ms
memory: 93712kb
input:
100 8000 6000 300083 476523 482608 21733 28565 486450 130857 230311 413484 166500 162587 260465 293137 250677 91590 495361 213360 89633 310942 46372 284836 308066 312348 22024 254554 461569 41723 400947 197082 286616 390455 302256 462378 481962 455426 45603 457483 404009 279406 207812 461602 279234 ...
output:
78
result:
ok single line: '78'
Test #28:
score: 0
Accepted
time: 11ms
memory: 93792kb
input:
100 8000 3000 349688 110364 204130 261795 399833 443387 7687 397959 231285 426706 308452 125270 252485 405799 90 6212 392185 196397 230660 90964 309814 58734 321188 94974 274155 258035 133847 137190 142104 270143 419182 422564 131482 172427 436081 120129 165426 468786 292634 422791 107056 157405 394...
output:
47
result:
ok single line: '47'
Test #29:
score: 0
Accepted
time: 14ms
memory: 95688kb
input:
100 8000 5000 432732 28718 32127 157910 400081 293228 282303 467763 177603 377587 436200 15806 290625 208627 320226 295877 97340 275915 225419 227052 425917 326666 203460 408584 69791 222820 24515 254501 384537 56310 391749 32870 230072 142265 218590 430854 215072 28096 199398 235671 96365 493361 48...
output:
70
result:
ok single line: '70'
Test #30:
score: 0
Accepted
time: 7ms
memory: 93688kb
input:
100 20000 7500 265668 267070 51164 288683 360507 70115 344194 159434 288683 288683 118552 204469 495058 260491 455254 288683 161325 148274 141485 316912 356624 270993 288683 270981 456336 288683 494888 243289 454834 386616 288683 160061 288683 102794 309555 179758 414065 480849 415057 288683 204579 ...
output:
65
result:
ok single line: '65'
Test #31:
score: 0
Accepted
time: 11ms
memory: 93752kb
input:
100 40000 12000 148990 264865 225361 15902 148990 387814 368692 148990 358572 154517 148990 148990 148990 148990 114698 148990 148990 148990 461229 148990 148990 148990 447993 166967 63548 148990 375511 149289 148990 148990 497498 148990 442420 148990 168189 295994 148990 148990 326163 457297 148990...
output:
76
result:
ok single line: '76'
Test #32:
score: 0
Accepted
time: 3ms
memory: 93752kb
input:
100 5 1 220 274 166 49 133 19 7 91 40 67 286 73 142 58 229 13 280 31 295 199 100 43 97 217 190 202 139 1 79 172 148 283 127 178 181 64 25 16 253 37 151 154 268 85 4 223 106 103 61 298 112 22 130 214 211 28 193 115 289 163 169 196 226 121 184 82 76 55 265 124 109 52 157 262 241 247 235 205 238 88 70 ...
output:
0
result:
ok single line: '0'
Test #33:
score: 0
Accepted
time: 9ms
memory: 93952kb
input:
100 2 1 199 214 271 253 274 262 289 16 181 1 76 250 88 298 19 232 190 85 175 178 7 79 172 133 202 142 166 259 187 34 136 241 286 13 31 28 112 226 43 205 127 40 52 4 67 220 139 208 151 229 10 25 121 292 277 295 49 148 97 115 160 82 145 196 268 100 193 184 256 244 265 91 247 163 157 238 64 109 235 283...
output:
0
result:
ok single line: '0'
Test #34:
score: 0
Accepted
time: 0ms
memory: 93792kb
input:
99 5 1 226 120 145 2 40 222 71 134 194 92 93 103 152 89 106 163 58 110 187 44 169 211 156 176 29 215 37 65 148 219 183 47 127 173 43 197 124 117 205 180 33 201 99 135 82 1 208 79 149 128 142 64 198 9 190 113 5 229 75 19 212 72 170 159 61 50 177 36 100 218 78 12 131 162 51 26 141 57 16 23 155 107 191...
output:
33
result:
ok single line: '33'
Test #35:
score: 0
Accepted
time: 15ms
memory: 93748kb
input:
100 500000 1 292 154 187 4 52 286 91 172 250 118 121 133 196 298 136 211 76 142 241 58 217 271 202 226 37 277 49 85 190 283 235 61 163 223 55 253 160 151 265 232 43 259 127 175 106 1 268 103 193 166 184 82 256 13 244 145 7 295 97 25 274 94 220 205 79 64 229 46 130 280 100 16 169 208 67 34 181 73 22 ...
output:
1
result:
ok single line: '1'
Test #36:
score: 0
Accepted
time: 10ms
memory: 93788kb
input:
100 2000 500 418148 67772 425443 340480 340480 340480 340480 340480 340480 316215 294520 338888 340480 100549 115089 340480 107308 340480 340480 340480 340480 340480 174618 18800 340480 301568 340480 340480 340480 340480 232718 340480 340480 259501 295002 340480 340480 138230 340480 41270 340480 194...
output:
66
result:
ok single line: '66'
Test #37:
score: 0
Accepted
time: 14ms
memory: 93748kb
input:
100 2000 300 377953 322264 413478 413478 376432 413478 413478 334955 233334 66253 413478 304735 413478 413478 21922 413478 413478 413478 413478 161562 413478 413478 413478 413478 91165 413478 460936 413478 418372 262631 413478 352490 224110 276955 413478 191376 39467 56781 413478 413478 460179 41347...
output:
58
result:
ok single line: '58'
Test #38:
score: 0
Accepted
time: 11ms
memory: 93696kb
input:
100 1300 500 275326 32201 43613 32201 32201 32201 32201 32201 32201 32201 109685 32201 32201 32201 317745 32201 32201 32201 32201 32201 481269 100696 214472 32201 10494 38972 434257 258191 32201 32201 32201 330759 461123 184513 312960 401127 32201 32201 379885 150822 32201 44681 150926 402532 20978 ...
output:
66
result:
ok single line: '66'
Test #39:
score: 0
Accepted
time: 10ms
memory: 93688kb
input:
100 1300 300 105199 105199 135094 238839 105199 105199 105199 105199 105199 114122 190730 105199 105199 251539 438687 80445 105199 400921 105199 105199 105199 105199 105199 105199 105199 105199 431617 105199 105199 469254 123139 350126 6811 372888 360852 93084 199402 105199 105199 105199 105199 1051...
output:
65
result:
ok single line: '65'
Test #40:
score: 0
Accepted
time: 3ms
memory: 95736kb
input:
100 2000 80 332966 226626 332966 225313 332966 332966 183595 332966 233583 332966 379780 449197 366550 332966 174233 332966 309128 332966 332966 199315 332966 43405 406348 455211 332966 332966 332966 110679 311635 332966 332966 332966 487496 332966 385059 332966 223471 239312 387602 332966 332966 10...
output:
54
result:
ok single line: '54'
Test #41:
score: 0
Accepted
time: 0ms
memory: 93692kb
input:
100 2000 130 384497 481777 50122 20784 343979 343979 398541 259243 65525 110266 343979 343979 343979 248299 343979 343979 343979 343979 493144 343979 452004 343979 343979 343979 343979 343979 150234 377797 196132 343979 343979 29893 424743 69112 343979 343979 229115 343979 343979 450379 343979 42121...
output:
55
result:
ok single line: '55'
Test #42:
score: 0
Accepted
time: 0ms
memory: 95804kb
input:
100 1300 50 397272 101950 473518 17739 473518 473518 473518 468065 250285 473518 166170 473518 473518 184167 224701 193447 473518 473518 473518 318583 222407 473518 317358 473518 473518 473518 473518 14161 473518 473518 100624 473518 473518 176415 473518 113482 462613 473518 449088 473518 473518 259...
output:
50
result:
ok single line: '50'
Test #43:
score: 0
Accepted
time: 8ms
memory: 93916kb
input:
100 1300 100 435913 93884 217777 145492 145492 280703 145492 340217 43451 145492 145492 314747 351065 340743 145492 145492 145492 477577 145492 176153 145492 284890 13898 145492 432377 145492 145492 235162 219042 145492 488155 145492 145492 145492 467400 299157 145492 145492 145492 142783 145492 145...
output:
52
result:
ok single line: '52'
Test #44:
score: 0
Accepted
time: 8ms
memory: 93748kb
input:
100 2000 1000 131926 62202 165169 131926 131926 393587 7138 46568 131926 131926 131926 131926 396926 234879 131926 131926 131926 328546 131926 131926 37402 328699 300984 456035 160067 400781 65346 131926 131926 131926 179303 331672 131926 186742 131926 131926 131926 250103 131926 131926 131926 21872...
output:
73
result:
ok single line: '73'
Test #45:
score: 0
Accepted
time: 0ms
memory: 93660kb
input:
100 1300 700 459203 224768 459203 459203 459203 459203 459203 172480 209823 23 459203 459203 459203 459203 459203 203877 459203 459203 399243 459203 445094 390194 51075 459203 29023 459203 235059 315626 459203 459203 408210 300568 24624 459203 459203 223172 459203 397353 277240 459203 459203 459203 ...
output:
75
result:
ok single line: '75'
Test #46:
score: 0
Accepted
time: 3ms
memory: 93628kb
input:
3 2 1 1 2 3 3 4 5
output:
0
result:
ok single line: '0'
Test #47:
score: 0
Accepted
time: 16ms
memory: 95772kb
input:
100 500000 499999 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 176385 17...
output:
100
result:
ok single line: '100'
Subtask #3:
score: 0
Time Limit Exceeded
Dependency #2:
100%
Accepted
Test #48:
score: 0
Time Limit Exceeded
input:
5000 233332 10000 421792 375018 481154 336831 239001 405616 387728 193044 450941 324370 238058 90659 431129 164919 47539 459063 498299 50838 171390 288397 159733 478192 6313 157409 366112 335593 328170 245357 341333 328352 250456 17602 438402 281715 81204 117468 456833 337362 432232 186808 408980 44...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #100:
score: 0
Runtime Error
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:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%