QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#133882	#3269. 末日魔法少女计划	zhouhuanyi	46.612728	3ms	5932kb	C++23	2.2kb	2023-08-02 16:26:49	2023-08-02 16:26:52

Judging History

This is the latest submission verdict.

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-08-02 16:26:52]
Judged

Verdict: 46.612728
Time: 3ms
Memory: 5932kb

Show

[2023-08-02 16:26:49]
Submitted

answer

#include<iostream>
#include<cstdio>
#include<vector>
#define N 100000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int x,y;
};
reads tong[N+1],tong2[N+1];
int n,k,sz,sn,length,length2,lst[N+1],ft[N+1];
void adder(int x,int y)
{
	tong[++length]=(reads){x,y};
	return;
}
void solve(int l,int r)
{
	if (r-l<=2) return;
	int mid=(l+r)>>1;
	for (int i=l;i<=mid-2;++i) adder(lst[i],lst[mid]);
	for (int i=mid+2;i<=r;++i) adder(lst[mid],lst[i]);
	if (l<=mid-1) solve(l,mid-1);
	if (mid+1<=r) solve(mid+1,r);
	return;
}
void solve2(int l,int r)
{
	if (r-l<=3) return;
	int mid=l+(r-l+1)/3,mid2=r-(r-l+1)/3;
	for (int i=l;i<=mid-2;++i) adder(lst[i],lst[mid]);
	for (int i=mid+2;i<=mid2-1;++i) adder(lst[mid],lst[i]);
	for (int i=mid+1;i<=mid2-2;++i) adder(lst[i],lst[mid2]);
	for (int i=mid2+2;i<=r;++i) adder(lst[mid2],lst[i]);
	if (mid2-mid>1) adder(lst[mid],lst[mid2]);
	if (l<=mid-1) solve2(l,mid-1);
	if (mid+1<=mid2-1) solve2(mid+1,mid2-1);
	if (mid2+1<=r) solve2(mid2+1,r);
	return;
}
int main()
{
	n=read()+1,k=read();
	if (k==2)
	{
		for (int i=1;i<=n;++i) lst[i]=i;
		solve(1,n);
	}
	else if (k==3)
	{
		for (int i=1;i<=n;++i) lst[i]=i;
		solve2(1,n);
	}
	else
	{
		sz=k+1,sn=(n+sz-1)/sz;
		for (int i=1;i<=sn;++i) lst[i]=min(i*sz,n);
		for (int i=1;i<=lst[1]-2;++i) adder(i,lst[1]);
		for (int i=1;i<=sn-1;++i)
		{
			for (int j=lst[i]+2;j<=lst[i+1];++j) adder(lst[i],j);
			for (int j=lst[i]+1;j<=lst[i+1]-2;++j) adder(j,lst[i+1]);
		}
		solve(1,sn),length2=length;
		for (int i=1;i<=length2;++i) tong2[i]=tong[i];
		sz=k>>1,sn=(n+sz-1)/sz,length=0;
		for (int i=1;i<=sn;++i) lst[i]=min(i*sz,n);
		for (int i=1;i<=lst[1]-2;++i) adder(i,lst[1]);
		for (int i=1;i<=sn-1;++i)
			for (int j=lst[i]+2;j<=lst[i+1];++j)
				adder(lst[i],j);
		if (k&1) solve2(1,sn);
		else solve(1,sn);
		if (length2<length)
		{
			length=length2;
			for (int i=1;i<=length;++i) tong[i]=tong2[i];
		}
	}
	printf("%d\n",length);
	for (int i=1;i<=length;++i) printf("%d %d\n",tong[i].x-1,tong[i].y-1);
	return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 22

Accepted

Test #1:

score: 22

Accepted

time: 1ms

memory: 3760kb

input:

2000 2

output:

result:

ok

Test #2:

score: 22

Accepted

time: 2ms

memory: 3792kb

input:

1999 2

output:

result:

ok

Test #3:

score: 22

Accepted

time: 3ms

memory: 3820kb

input:

1992 2

output:

result:

ok

Test #4:

score: 22

Accepted

time: 3ms

memory: 5628kb

input:

1973 2

output:

result:

ok

Test #5:

score: 22

Accepted

time: 0ms

memory: 3960kb

input:

1936 2

output:

result:

ok

Subtask #2:

score: 1.90513

Acceptable Answer

Test #6:

score: 2.01146

Acceptable Answer

time: 2ms

memory: 3772kb

input:

1936 3

output:

result:

points 0.14367574180

Test #7:

score: 1.90513

Acceptable Answer

time: 1ms

memory: 3772kb

input:

2000 3

output:

result:

points 0.136080540

Test #8:

score: 1.91402

Acceptable Answer

time: 2ms

memory: 4012kb

input:

1999 3

output:

result:

points 0.13671546740

Test #9:

score: 1.92094

Acceptable Answer

time: 2ms

memory: 3728kb

input:

1992 3

output:

result:

points 0.13720972280

Test #10:

score: 1.96504

Acceptable Answer

time: 3ms

memory: 3796kb

input:

1973 3

output:

result:

points 0.14035993820

Subtask #3:

score: 8.20221

Acceptable Answer

Test #11:

score: 8.20221

Acceptable Answer

time: 2ms

memory: 5720kb

input:

2000 4

output:

result:

points 0.74565544650

Test #12:

score: 8.22237

Acceptable Answer

time: 2ms

memory: 3684kb

input:

1999 4

output:

result:

points 0.74748808920

Test #13:

score: 8.22059

Acceptable Answer

time: 2ms

memory: 5588kb

input:

1991 4

output:

result:

points 0.74732617960

Test #14:

score: 8.24383

Acceptable Answer

time: 2ms

memory: 3736kb

input:

1971 4

output:

result:

points 0.74943874730

Test #15:

score: 8.29136

Acceptable Answer

time: 2ms

memory: 3768kb

input:

1938 4

output:

result:

points 0.7537597660

Subtask #4:

score: 4.66381

Acceptable Answer

Test #16:

score: 4.6648

Acceptable Answer

time: 2ms

memory: 3756kb

input:

2000 5

output:

result:

points 0.51831080840

Test #17:

score: 4.66381

Acceptable Answer

time: 0ms

memory: 5932kb

input:

1999 5

output:

result:

points 0.51820066550

Test #18:

score: 4.66401

Acceptable Answer

time: 2ms

memory: 3724kb

input:

1992 5

output:

result:

points 0.51822365770

Test #19:

score: 4.68602

Acceptable Answer

time: 2ms

memory: 3688kb

input:

1973 5

output:

result:

points 0.52066891430

Test #20:

score: 4.70777

Acceptable Answer

time: 2ms

memory: 3932kb

input:

1936 5

output:

result:

points 0.5230853060

Subtask #5:

score: 2.33503

Acceptable Answer

Test #21:

score: 2.3366

Acceptable Answer

time: 1ms

memory: 3772kb

input:

2000 6

output:

result:

points 0.33380035030

Test #22:

score: 2.33503

Acceptable Answer

time: 2ms

memory: 3752kb

input:

1997 6

output:

result:

points 0.33357615540

Test #23:

score: 2.3374

Acceptable Answer

time: 1ms

memory: 5716kb

input:

1989 6

output:

result:

points 0.33391439540

Test #24:

score: 2.34832

Acceptable Answer

time: 2ms

memory: 3636kb

input:

1972 6

output:

result:

points 0.33547359380

Test #25:

score: 2.36136

Acceptable Answer

time: 2ms

memory: 3696kb

input:

1933 6

output:

result:

points 0.33733679380

Subtask #6:

score: 1.55014

Acceptable Answer

Test #26:

score: 1.55084

Acceptable Answer

time: 1ms

memory: 3564kb

input:

1999 7

output:

result:

points 0.25847314120

Test #27:

score: 1.55014

Acceptable Answer

time: 1ms

memory: 3632kb

input:

1997 7

output:

result:

points 0.25835701460

Test #28:

score: 1.55085

Acceptable Answer

time: 1ms

memory: 3764kb

input:

1987 7

output:

result:

points 0.25847419380

Test #29:

score: 1.55191

Acceptable Answer

time: 2ms

memory: 3676kb

input:

1978 7

output:

result:

points 0.25865115430

Test #30:

score: 1.56099

Acceptable Answer

time: 2ms

memory: 3736kb

input:

1931 7

output:

result:

points 0.26016520850

Subtask #7:

score: 0.637525

Acceptable Answer

Test #31:

score: 0.640006

Acceptable Answer

time: 2ms

memory: 3736kb

input:

1995 8

output:

result:

points 0.12800125240

Test #32:

score: 0.637525

Acceptable Answer

time: 2ms

memory: 3968kb

input:

1999 8

output:

result:

points 0.12750504310

Test #33:

score: 0.641548

Acceptable Answer

time: 1ms

memory: 3744kb

input:

1987 8

output:

result:

points 0.12830963620

Test #34:

score: 0.640116

Acceptable Answer

time: 1ms

memory: 3968kb

input:

1981 8

output:

result:

points 0.12802311980

Test #35:

score: 0.650789

Acceptable Answer

time: 1ms

memory: 3904kb

input:

1923 8

output:

result:

points 0.13015789430

Subtask #8:

score: 0.954093

Acceptable Answer

Test #36:

score: 0.966888

Acceptable Answer

time: 0ms

memory: 3736kb

input:

1997 9

output:

result:

points 0.19337768110

Test #37:

score: 0.968154

Acceptable Answer

time: 0ms

memory: 5828kb

input:

1998 9

output:

result:

points 0.19363085410

Test #38:

score: 0.976205

Acceptable Answer

time: 1ms

memory: 3756kb

input:

1990 9

output:

result:

points 0.19524091540

Test #39:

score: 0.988555

Acceptable Answer

time: 1ms

memory: 3684kb

input:

1975 9

output:

result:

points 0.19771095220

Test #40:

score: 0.954093

Acceptable Answer

time: 1ms

memory: 3864kb

input:

1934 9

output:

result:

points 0.19081862140

Subtask #9:

score: 0.478085

Acceptable Answer

Test #41:

score: 0.478085

Acceptable Answer

time: 2ms

memory: 5660kb

input:

1995 10

output:

result:

points 0.11952114230

Test #42:

score: 0.47907

Acceptable Answer

time: 2ms

memory: 5832kb

input:

1996 10

output:

result:

points 0.11976748410

Test #43:

score: 0.487252

Acceptable Answer

time: 1ms

memory: 3964kb

input:

1979 10

output:

result:

points 0.12181291470

Test #44:

score: 0.486588

Acceptable Answer

time: 1ms

memory: 3692kb

input:

1972 10

output:

result:

points 0.12164693640

Test #45:

score: 0.491287

Acceptable Answer

time: 2ms

memory: 5608kb

input:

1945 10

output:

result:

points 0.12282166930

Subtask #10:

score: 0.863974

Acceptable Answer

Test #46:

score: 0.872236

Acceptable Answer

time: 1ms

memory: 3756kb

input:

1993 11

output:

result:

points 0.21805901940

Test #47:

score: 0.873105

Acceptable Answer

time: 1ms

memory: 3644kb

input:

1994 11

output:

result:

points 0.21827624210

Test #48:

score: 0.863974

Acceptable Answer

time: 2ms

memory: 5656kb

input:

2000 11

output:

result:

points 0.21599359450

Test #49:

score: 0.878026

Acceptable Answer

time: 0ms

memory: 3900kb

input:

1972 11

output:

result:

points 0.21950647780

Test #50:

score: 0.892549

Acceptable Answer

time: 2ms

memory: 3688kb

input:

1944 11

output:

result:

points 0.2231371330

Subtask #11:

score: 0.66905

Acceptable Answer

Test #51:

score: 0.66905

Acceptable Answer

time: 1ms

memory: 3964kb

input:

1999 12

output:

result:

points 0.16726243680

Test #52:

score: 0.669923

Acceptable Answer

time: 0ms

memory: 3620kb

input:

2000 12

output:

result:

points 0.16748066180

Test #53:

score: 0.674285

Acceptable Answer

time: 1ms

memory: 3732kb

input:

1989 12

output:

result:

points 0.16857112510

Test #54:

score: 0.676939

Acceptable Answer

time: 0ms

memory: 3740kb

input:

1976 12

output:

result:

points 0.16923475890

Test #55:

score: 0.68865

Acceptable Answer

time: 1ms

memory: 3676kb

input:

1949 12

output:

result:

points 0.17216256290

Subtask #12:

score: 0.753313

Acceptable Answer

Test #56:

score: 0.780592

Acceptable Answer

time: 1ms

memory: 3692kb

input:

1981 13

output:

result:

points 0.26019724060

Test #57:

score: 0.781164

Acceptable Answer

time: 1ms

memory: 5652kb

input:

1982 13

output:

result:

points 0.2603879390

Test #58:

score: 0.784147

Acceptable Answer

time: 1ms

memory: 3912kb

input:

1989 13

output:

result:

points 0.26138244440

Test #59:

score: 0.775423

Acceptable Answer

time: 0ms

memory: 3752kb

input:

1972 13

output:

result:

points 0.25847448010

Test #60:

score: 0.753313

Acceptable Answer

time: 2ms

memory: 3736kb

input:

1929 13

output:

result:

points 0.25110429830

Subtask #13:

score: 0.670348

Acceptable Answer

Test #61:

score: 0.671476

Acceptable Answer

time: 1ms

memory: 3680kb

input:

1979 14

output:

result:

points 0.22382523620

Test #62:

score: 0.672065

Acceptable Answer

time: 1ms

memory: 3684kb

input:

1980 14

output:

result:

points 0.22402175210

Test #63:

score: 0.670348

Acceptable Answer

time: 1ms

memory: 3676kb

input:

1987 14

output:

result:

points 0.22344943280

Test #64:

score: 0.679069

Acceptable Answer

time: 1ms

memory: 3688kb

input:

1952 14

output:

result:

points 0.22635644860

Test #65:

score: 0.681456

Acceptable Answer

time: 1ms

memory: 3620kb

input:

1936 14

output:

result:

points 0.22715192860

Subtask #14:

score: 0.930021

Acceptable Answer

Test #66:

score: 0.930532

Acceptable Answer

time: 2ms

memory: 5656kb

input:

2000 15

output:

result:

points 0.31017746430

Test #67:

score: 0.930021

Acceptable Answer

time: 0ms

memory: 5792kb

input:

1999 15

output:

result:

points 0.31000713210

Test #68:

score: 0.93412

Acceptable Answer

time: 2ms

memory: 5908kb

input:

1992 15

output:

result:

points 0.31137333340

Test #69:

score: 0.934296

Acceptable Answer

time: 1ms

memory: 3708kb

input:

1973 15

output:

result:

points 0.31143188150

Test #70:

score: 0.936317

Acceptable Answer

time: 1ms

memory: 3728kb

input:

1936 15

output:

result:

points 0.31210560670