QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#179043#5378. 匹配问题Lynkcat#4 24ms173664kbC++203.1kb2023-09-14 17:08:082024-07-04 02:00:11

Judging History

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

  • [2024-07-04 02:00:11]
  • 评测
  • 测评结果:4
  • 用时:24ms
  • 内存:173664kb
  • [2023-09-14 17:08:08]
  • 提交

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 1e9
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
#define N 2000005
#define M 2000005
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;
}	
const int B=100;
void Add(int x,int l,int r,int y)
{
    if (l>r) return;
    // cout<<x<<" "<<l<<" "<<r<<" "<<y<<endl;
    if (r-l+1<=B)
    {
        for (int i=l;i<=r;i++) add(x,i+n,1,-y);
        return;
    }
    add(x,l+2*n,1,-y);
    add(x,r+3*n,1,-y);
    r-=r%B;
    for (int i=l+(B-i%B)%B;i<=r;)
    {
        add(x,i+2*n,1,-y);
        i+=B;
    }
}
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=4*n+2;
    S=4*n+1,T=4*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++)
    {
        add(i+2*n,i+n,1,0);
        // cout<<i+2*n<<" "<<i+n<<endl;
        if (i<n&&i%B!=0)
            add(i+2*n,i+1+2*n,inf,0);
    }
    for (int i=1;i<=n;i++)
    {
        add(i+3*n,i+n,1,0);
        // cout<<i+3*n<<" "<<i+n<<endl;
        if (i>1&&i%B!=1)
            add(i+3*n,i-1+3*n,inf,0);
    }
    for (int i=1;i<=n;i++)
    {
        int l=n+1,mid=n+1,r=n+1;
        for (int j=n;j>=1;j--)
        {
            if (b[j]>=a[i]&&b[j]<=a[i]+lb)
            {
                l=j;
            } else
            if (b[j]>=a[i]&&b[j]<=a[i]+la)
            {
                mid=j;
            } else
            if (b[j]>a[i]+la)
                r=j;
        }
        // cout<<i<<" "<<l<<" "<<mid<<" "<<r<<endl;
        Add(i,l,mid-1,1);
        Add(i,mid,r-1,0);
    }
    while (spfa());
    cout<<-MC<<'\n';
}
signed main()
{
    IOS;
    cin.tie(0);
    int T=1;
    while (T--)
    {
        BellaKira();
    }
}

詳細信息

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 15ms
memory: 171456kb

input:

2 2 1
1 1
1 1

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 7ms
memory: 171452kb

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: 18ms
memory: 171736kb

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: 171608kb

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: 12ms
memory: 171804kb

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: 24ms
memory: 173616kb

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: 15ms
memory: 171508kb

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: 8ms
memory: 171804kb

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: 4ms
memory: 171732kb

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: 12ms
memory: 171740kb

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: 12ms
memory: 171576kb

input:

3 2 1
1 2 3
3 4 5

output:

0

result:

ok single line: '0'

Test #12:

score: 0
Accepted
time: 0ms
memory: 171736kb

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: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #13:

score: 14
Accepted
time: 7ms
memory: 171512kb

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: 19ms
memory: 171520kb

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: 7ms
memory: 171584kb

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: 8ms
memory: 173664kb

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: 7ms
memory: 171556kb

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: 173568kb

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: 12ms
memory: 171740kb

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: 12ms
memory: 173564kb

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: 11ms
memory: 173564kb

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: 14ms
memory: 173508kb

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: -14
Wrong Answer
time: 7ms
memory: 171816kb

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:

66

result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

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:

0%