QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#133916	#3269. 末日魔法少女计划	zhouhuanyi	55.714961	3ms	5724kb	C++23	2.3kb	2023-08-02 17:17:14	2023-08-02 17:17:14

Judging History

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

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

[2023-08-02 17:17:14]
评测

测评结果：55.714961
用时：3ms
内存：5724kb

查看

[2023-08-02 17:17:14]
提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#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+(int)(floor((r-l)*2.0/3+0.5)),cnt=0,cnt2=0;
	for (int i=l;i<=mid-2;++i) cnt+=(i&1);
	for (int i=mid+2;i<=r;++i) cnt2+=(i&1);
	if (cnt<cnt2)
	{
		for (int i=l;i<=mid-2;++i) adder(lst[i],lst[mid]);
		for (int i=mid+2;i<=r;++i)
			if (!(i&1))
				adder(lst[mid],lst[i]);
	}
	else
	{
		for (int i=l;i<=mid-2;++i)
			if (!(i&1))
				adder(lst[i],lst[mid]);
		for (int i=mid+2;i<=r;++i) adder(lst[mid],lst[i]);
	}
	if (l<=mid-1) solve2(l,mid-1);
	if (mid+1<=r) solve2(mid+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;
		for (int i=2;i+2<=n;i+=2) adder(lst[i],lst[i+2]);
		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-2,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);
		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: 3ms

memory: 5720kb

input:

2000 2

output:

result:

ok

Test #2:

score: 22

Accepted

time: 3ms

memory: 3796kb

input:

1999 2

output:

result:

ok

Test #3:

score: 22

Accepted

time: 3ms

memory: 4032kb

input:

1992 2

output:

result:

ok

Test #4:

score: 22

Accepted

time: 3ms

memory: 5724kb

input:

1973 2

output:

result:

ok

Test #5:

score: 22

Accepted

time: 2ms

memory: 3888kb

input:

1936 2

output:

result:

ok

Subtask #2:

score: 2.82415

Acceptable Answer

Test #6:

score: 2.91468

Acceptable Answer

time: 2ms

memory: 3768kb

input:

1936 3

output:

result:

points 0.20819130710

Test #7:

score: 2.83899

Acceptable Answer

time: 2ms

memory: 3776kb

input:

2000 3

output:

result:

points 0.20278481290

Test #8:

score: 2.83757

Acceptable Answer

time: 0ms

memory: 5720kb

input:

1999 3

output:

result:

points 0.20268357290

Test #9:

score: 2.82415

Acceptable Answer

time: 2ms

memory: 3900kb

input:

1992 3

output:

result:

points 0.20172468840

Test #10:

score: 2.84579

Acceptable Answer

time: 3ms

memory: 5588kb

input:

1973 3

output:

result:

points 0.20327048680

Subtask #3:

score: 8.20221

Acceptable Answer

Test #11:

score: 8.20221

Acceptable Answer

time: 2ms

memory: 3904kb

input:

2000 4

output:

result:

points 0.74565544650

Test #12:

score: 8.22237

Acceptable Answer

time: 2ms

memory: 3732kb

input:

1999 4

output:

result:

points 0.74748808920

Test #13:

score: 8.22059

Acceptable Answer

time: 1ms

memory: 3796kb

input:

1991 4

output:

result:

points 0.74732617960

Test #14:

score: 8.24383

Acceptable Answer

time: 2ms

memory: 5608kb

input:

1971 4

output:

result:

points 0.74943874730

Test #15:

score: 8.29136

Acceptable Answer

time: 0ms

memory: 3896kb

input:

1938 4

output:

result:

points 0.7537597660

Subtask #4:

score: 4.66381

Acceptable Answer

Test #16:

score: 4.6648

Acceptable Answer

time: 1ms

memory: 3748kb

input:

2000 5

output:

result:

points 0.51831080840

Test #17:

score: 4.66381

Acceptable Answer

time: 1ms

memory: 3984kb

input:

1999 5

output:

result:

points 0.51820066550

Test #18:

score: 4.66401

Acceptable Answer

time: 1ms

memory: 3748kb

input:

1992 5

output:

result:

points 0.51822365770

Test #19:

score: 4.68602

Acceptable Answer

time: 1ms

memory: 3848kb

input:

1973 5

output:

result:

points 0.52066891430

Test #20:

score: 4.70777

Acceptable Answer

time: 2ms

memory: 3632kb

input:

1936 5

output:

result:

points 0.5230853060

Subtask #5:

score: 2.56111

Acceptable Answer

Test #21:

score: 2.56111

Acceptable Answer

time: 1ms

memory: 3924kb

input:

2000 6

output:

result:

points 0.36587351250

Test #22:

score: 2.56497

Acceptable Answer

time: 0ms

memory: 3976kb

input:

1997 6

output:

result:

points 0.36642489970

Test #23:

score: 2.56841

Acceptable Answer

time: 0ms

memory: 3760kb

input:

1989 6

output:

result:

points 0.36691632330

Test #24:

score: 2.5732

Acceptable Answer

time: 2ms

memory: 3624kb

input:

1972 6

output:

result:

points 0.36760066840

Test #25:

score: 2.59337

Acceptable Answer

time: 2ms

memory: 3756kb

input:

1933 6

output:

result:

points 0.37048160140

Subtask #6:

score: 2.48052

Acceptable Answer

Test #26:

score: 2.48387

Acceptable Answer

time: 2ms

memory: 3700kb

input:

1999 7

output:

result:

points 0.41397901850

Test #27:

score: 2.48052

Acceptable Answer

time: 0ms

memory: 3672kb

input:

1997 7

output:

result:

points 0.41342003780

Test #28:

score: 2.48494

Acceptable Answer

time: 1ms

memory: 3700kb

input:

1987 7

output:

result:

points 0.41415663210

Test #29:

score: 2.4911

Acceptable Answer

time: 0ms

memory: 3764kb

input:

1978 7

output:

result:

points 0.41518397560

Test #30:

score: 2.50844

Acceptable Answer

time: 1ms

memory: 3872kb

input:

1931 7

output:

result:

points 0.4180729170

Subtask #7:

score: 1.84948

Acceptable Answer

Test #31:

score: 1.85423

Acceptable Answer

time: 0ms

memory: 3916kb

input:

1995 8

output:

result:

points 0.37084653480

Test #32:

score: 1.84948

Acceptable Answer

time: 0ms

memory: 3684kb

input:

1999 8

output:

result:

points 0.36989663260

Test #33:

score: 1.85423

Acceptable Answer

time: 2ms

memory: 3644kb

input:

1987 8

output:

result:

points 0.37084557550

Test #34:

score: 1.85662

Acceptable Answer

time: 0ms

memory: 3692kb

input:

1981 8

output:

result:

points 0.37132490180

Test #35:

score: 1.88399

Acceptable Answer

time: 2ms

memory: 3660kb

input:

1923 8

output:

result:

points 0.37679787060

Subtask #8:

score: 2.07348

Acceptable Answer

Test #36:

score: 2.07348

Acceptable Answer

time: 2ms

memory: 5652kb

input:

1997 9

output:

result:

points 0.41469539130

Test #37:

score: 2.07456

Acceptable Answer

time: 1ms

memory: 3664kb

input:

1998 9

output:

result:

points 0.41491256870

Test #38:

score: 2.0766

Acceptable Answer

time: 0ms

memory: 3684kb

input:

1990 9

output:

result:

points 0.41531960960

Test #39:

score: 2.08182

Acceptable Answer

time: 1ms

memory: 3756kb

input:

1975 9

output:

result:

points 0.41636397520

Test #40:

score: 2.10251

Acceptable Answer

time: 1ms

memory: 3728kb

input:

1934 9

output:

result:

points 0.42050174410

Subtask #9:

score: 1.57605

Acceptable Answer

Test #41:

score: 1.57605

Acceptable Answer

time: 1ms

memory: 3644kb

input:

1995 10

output:

result:

points 0.3940133850

Test #42:

score: 1.57681

Acceptable Answer

time: 1ms

memory: 3740kb

input:

1996 10

output:

result:

points 0.39420262370

Test #43:

score: 1.57901

Acceptable Answer

time: 0ms

memory: 5636kb

input:

1979 10

output:

result:

points 0.39475246390

Test #44:

score: 1.58127

Acceptable Answer

time: 1ms

memory: 3636kb

input:

1972 10

output:

result:

points 0.39531817670

Test #45:

score: 1.58353

Acceptable Answer

time: 1ms

memory: 3736kb

input:

1945 10

output:

result:

points 0.39588254670

Subtask #10:

score: 1.66752

Acceptable Answer

Test #46:

score: 1.67067

Acceptable Answer

time: 1ms

memory: 3680kb

input:

1993 11

output:

result:

points 0.41766843470

Test #47:

score: 1.67137

Acceptable Answer

time: 1ms

memory: 3752kb

input:

1994 11

output:

result:

points 0.41784283990

Test #48:

score: 1.66752

Acceptable Answer

time: 1ms

memory: 3748kb

input:

2000 11

output:

result:

points 0.41688078040

Test #49:

score: 1.67213

Acceptable Answer

time: 1ms

memory: 3612kb

input:

1972 11

output:

result:

points 0.41803303430

Test #50:

score: 1.67688

Acceptable Answer

time: 1ms

memory: 3892kb

input:

1944 11

output:

result:

points 0.41922086660

Subtask #11:

score: 1.69004

Acceptable Answer

Test #51:

score: 1.69779

Acceptable Answer

time: 0ms

memory: 3756kb

input:

1999 12

output:

result:

points 0.42444798660

Test #52:

score: 1.69004

Acceptable Answer

time: 1ms

memory: 3640kb

input:

2000 12

output:

result:

points 0.42251022370

Test #53:

score: 1.69987

Acceptable Answer

time: 0ms

memory: 3864kb

input:

1989 12

output:

result:

points 0.42496673240

Test #54:

score: 1.70004

Acceptable Answer

time: 1ms

memory: 3752kb

input:

1976 12

output:

result:

points 0.42501121650

Test #55:

score: 1.7084

Acceptable Answer

time: 1ms

memory: 3728kb

input:

1949 12

output:

result:

points 0.42709986410

Subtask #12:

score: 1.3113

Acceptable Answer

Test #56:

score: 1.3113

Acceptable Answer

time: 1ms

memory: 3684kb

input:

1981 13

output:

result:

points 0.43709860820

Test #57:

score: 1.31174

Acceptable Answer

time: 1ms

memory: 3964kb

input:

1982 13

output:

result:

points 0.4372459450

Test #58:

score: 1.31482

Acceptable Answer

time: 1ms

memory: 3748kb

input:

1989 13

output:

result:

points 0.43827422850

Test #59:

score: 1.31398

Acceptable Answer

time: 1ms

memory: 3728kb

input:

1972 13

output:

result:

points 0.43799219860

Test #60:

score: 1.32184

Acceptable Answer

time: 0ms

memory: 3728kb

input:

1929 13

output:

result:

points 0.44061395220

Subtask #13:

score: 1.37609

Acceptable Answer

Test #61:

score: 1.38268

Acceptable Answer

time: 1ms

memory: 3616kb

input:

1979 14

output:

result:

points 0.46089328330

Test #62:

score: 1.37609

Acceptable Answer

time: 1ms

memory: 3692kb

input:

1980 14

output:

result:

points 0.45869603740

Test #63:

score: 1.37897

Acceptable Answer

time: 1ms

memory: 3896kb

input:

1987 14

output:

result:

points 0.45965524060

Test #64:

score: 1.38567

Acceptable Answer

time: 2ms

memory: 5636kb

input:

1952 14

output:

result:

points 0.46189075520

Test #65:

score: 1.38616

Acceptable Answer

time: 1ms

memory: 3684kb

input:

1936 14

output:

result:

points 0.46205183180

Subtask #14:

score: 1.4392

Acceptable Answer

Test #66:

score: 1.44226

Acceptable Answer

time: 2ms

memory: 5700kb

input:

2000 15

output:

result:

points 0.48075275040

Test #67:

score: 1.44188

Acceptable Answer

time: 1ms

memory: 3620kb

input:

1999 15

output:

result:

points 0.48062579680

Test #68:

score: 1.4392

Acceptable Answer

time: 0ms

memory: 3748kb

input:

1992 15

output:

result:

points 0.4797344270

Test #69:

score: 1.44657

Acceptable Answer

time: 1ms

memory: 3904kb

input:

1973 15

output:

result:

points 0.48219141220

Test #70:

score: 1.45467

Acceptable Answer

time: 1ms

memory: 3736kb

input:

1936 15

output:

result:

points 0.48488838710