QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#133871	#3269. 末日魔法少女计划	zhouhuanyi	35.038017	3ms	3952kb	C++23	1.5kb	2023-08-02 16:08:23	2023-08-02 16:08:25

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:08:25]
Judged

Verdict: 35.038017
Time: 3ms
Memory: 3952kb

Show

[2023-08-02 16:08:23]
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];
int n,k,sz,sn,length,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(),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<=sn-1;++i)
		for (int j=lst[i]+2;j<=lst[i+1];++j)
			adder(lst[i],j);
	if (!(k&1)) solve(1,sn);
	else solve2(1,sn);
	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;
}

源文件, 语言: C++23

详细

Subtask #1:

score: 22

Accepted

Test #1:

score: 22

Accepted

time: 0ms

memory: 3676kb

input:

2000 2

output:

result:

ok

Test #2:

score: 22

Accepted

time: 3ms

memory: 3740kb

input:

1999 2

output:

result:

ok

Test #3:

score: 22

Accepted

time: 3ms

memory: 3744kb

input:

1992 2

output:

result:

ok

Test #4:

score: 22

Accepted

time: 3ms

memory: 3676kb

input:

1973 2

output:

result:

ok

Test #5:

score: 22

Accepted

time: 3ms

memory: 3916kb

input:

1936 2

output:

result:

ok

Subtask #2:

score: 1.90513

Acceptable Answer

Test #6:

score: 2.01146

Acceptable Answer

time: 2ms

memory: 3784kb

input:

1936 3

output:

result:

points 0.14367574180

Test #7:

score: 1.90513

Acceptable Answer

time: 0ms

memory: 3772kb

input:

2000 3

output:

result:

points 0.136080540

Test #8:

score: 1.91402

Acceptable Answer

time: 0ms

memory: 3736kb

input:

1999 3

output:

result:

points 0.13671546740

Test #9:

score: 1.92094

Acceptable Answer

time: 0ms

memory: 3792kb

input:

1992 3

output:

result:

points 0.13720972280

Test #10:

score: 1.96504

Acceptable Answer

time: 2ms

memory: 3716kb

input:

1973 3

output:

result:

points 0.14035993820

Subtask #3:

score: 2.00683

Acceptable Answer

Test #11:

score: 2.00683

Acceptable Answer

time: 0ms

memory: 3608kb

input:

2000 4

output:

result:

points 0.18243919120

Test #12:

score: 2.01245

Acceptable Answer

time: 2ms

memory: 3724kb

input:

1999 4

output:

result:

points 0.18295042250

Test #13:

score: 2.01815

Acceptable Answer

time: 2ms

memory: 3896kb

input:

1991 4

output:

result:

points 0.18346833250

Test #14:

score: 2.03261

Acceptable Answer

time: 2ms

memory: 3716kb

input:

1971 4

output:

result:

points 0.18478297580

Test #15:

score: 2.05208

Acceptable Answer

time: 0ms

memory: 3744kb

input:

1938 4

output:

result:

points 0.18655287680

Subtask #4:

score: 1.29368

Acceptable Answer

Test #16:

score: 1.35762

Acceptable Answer

time: 2ms

memory: 3712kb

input:

2000 5

output:

result:

points 0.1508470790

Test #17:

score: 1.38284

Acceptable Answer

time: 2ms

memory: 3712kb

input:

1999 5

output:

result:

points 0.15364933090

Test #18:

score: 1.41892

Acceptable Answer

time: 0ms

memory: 3716kb

input:

1992 5

output:

result:

points 0.15765751250

Test #19:

score: 1.3794

Acceptable Answer

time: 2ms

memory: 3952kb

input:

1973 5

output:

result:

points 0.15326650470

Test #20:

score: 1.29368

Acceptable Answer

time: 2ms

memory: 3728kb

input:

1936 5

output:

result:

points 0.14374237570

Subtask #5:

score: 0.896142

Acceptable Answer

Test #21:

score: 0.896142

Acceptable Answer

time: 2ms

memory: 3724kb

input:

2000 6

output:

result:

points 0.12802030760

Test #22:

score: 0.898039

Acceptable Answer

time: 2ms

memory: 3620kb

input:

1997 6

output:

result:

points 0.1282913090

Test #23:

score: 0.897263

Acceptable Answer

time: 2ms

memory: 3712kb

input:

1989 6

output:

result:

points 0.12818039350

Test #24:

score: 0.911131

Acceptable Answer

time: 1ms

memory: 3616kb

input:

1972 6

output:

result:

points 0.13016162010

Test #25:

score: 0.937026

Acceptable Answer

time: 0ms

memory: 3660kb

input:

1933 6

output:

result:

points 0.13386079720

Subtask #6:

score: 1.04301

Acceptable Answer

Test #26:

score: 1.04301

Acceptable Answer

time: 2ms

memory: 3936kb

input:

1999 7

output:

result:

points 0.17383424650

Test #27:

score: 1.04942

Acceptable Answer

time: 2ms

memory: 3704kb

input:

1997 7

output:

result:

points 0.17490301020

Test #28:

score: 1.05144

Acceptable Answer

time: 2ms

memory: 3652kb

input:

1987 7

output:

result:

points 0.17523997310

Test #29:

score: 1.06292

Acceptable Answer

time: 1ms

memory: 3704kb

input:

1978 7

output:

result:

points 0.17715320390

Test #30:

score: 1.08977

Acceptable Answer

time: 2ms

memory: 3860kb

input:

1931 7

output:

result:

points 0.18162898950

Subtask #7:

score: 0.5459

Acceptable Answer

Test #31:

score: 0.547026

Acceptable Answer

time: 2ms

memory: 3584kb

input:

1995 8

output:

result:

points 0.10940517970

Test #32:

score: 0.5459

Acceptable Answer

time: 0ms

memory: 3612kb

input:

1999 8

output:

result:

points 0.10918000860

Test #33:

score: 0.549292

Acceptable Answer

time: 2ms

memory: 3652kb

input:

1987 8

output:

result:

points 0.10985841430

Test #34:

score: 0.547613

Acceptable Answer

time: 2ms

memory: 3652kb

input:

1981 8

output:

result:

points 0.10952254870

Test #35:

score: 0.568145

Acceptable Answer

time: 2ms

memory: 3712kb

input:

1923 8

output:

result:

points 0.11362899230

Subtask #8:

score: 0.956761

Acceptable Answer

Test #36:

score: 0.96948

Acceptable Answer

time: 0ms

memory: 3716kb

input:

1997 9

output:

result:

points 0.19389604460

Test #37:

score: 0.970746

Acceptable Answer

time: 0ms

memory: 3580kb

input:

1998 9

output:

result:

points 0.19414912090

Test #38:

score: 0.978812

Acceptable Answer

time: 0ms

memory: 3720kb

input:

1990 9

output:

result:

points 0.19576230810

Test #39:

score: 0.99119

Acceptable Answer

time: 0ms

memory: 3700kb

input:

1975 9

output:

result:

points 0.19823792460

Test #40:

score: 0.956761

Acceptable Answer

time: 1ms

memory: 3576kb

input:

1934 9

output:

result:

points 0.19135218230

Subtask #9:

score: 0.481193

Acceptable Answer

Test #41:

score: 0.481193

Acceptable Answer

time: 2ms

memory: 3708kb

input:

1995 10

output:

result:

points 0.1202981510

Test #42:

score: 0.482177

Acceptable Answer

time: 1ms

memory: 3600kb

input:

1996 10

output:

result:

points 0.12054432090

Test #43:

score: 0.490393

Acceptable Answer

time: 2ms

memory: 3868kb

input:

1979 10

output:

result:

points 0.12259825420

Test #44:

score: 0.48974

Acceptable Answer

time: 1ms

memory: 3820kb

input:

1972 10

output:

result:

points 0.12243491580

Test #45:

score: 0.494487

Acceptable Answer

time: 1ms

memory: 3580kb

input:

1945 10

output:

result:

points 0.12362166310

Subtask #10:

score: 0.867551

Acceptable Answer

Test #46:

score: 0.875835

Acceptable Answer

time: 1ms

memory: 3688kb

input:

1993 11

output:

result:

points 0.21895866870

Test #47:

score: 0.876703

Acceptable Answer

time: 0ms

memory: 3684kb

input:

1994 11

output:

result:

points 0.219175690

Test #48:

score: 0.867551

Acceptable Answer

time: 1ms

memory: 3920kb

input:

2000 11

output:

result:

points 0.21688772870

Test #49:

score: 0.88167

Acceptable Answer

time: 2ms

memory: 3684kb

input:

1972 11

output:

result:

points 0.22041740130

Test #50:

score: 0.896262

Acceptable Answer

time: 0ms

memory: 3640kb

input:

1944 11

output:

result:

points 0.22406550830

Subtask #11:

score: 0.673699

Acceptable Answer

Test #51:

score: 0.673699

Acceptable Answer

time: 1ms

memory: 3688kb

input:

1999 12

output:

result:

points 0.16842463910

Test #52:

score: 0.67457

Acceptable Answer

time: 1ms

memory: 3712kb

input:

2000 12

output:

result:

points 0.16864258740

Test #53:

score: 0.678964

Acceptable Answer

time: 1ms

memory: 3640kb

input:

1989 12

output:

result:

points 0.16974101580

Test #54:

score: 0.681653

Acceptable Answer

time: 0ms

memory: 3640kb

input:

1976 12

output:

result:

points 0.17041329370

Test #55:

score: 0.693447

Acceptable Answer

time: 2ms

memory: 3912kb

input:

1949 12

output:

result:

points 0.1733616680

Subtask #12:

score: 0.757421

Acceptable Answer

Test #56:

score: 0.784641

Acceptable Answer

time: 1ms

memory: 3576kb

input:

1981 13

output:

result:

points 0.2615469660

Test #57:

score: 0.785212

Acceptable Answer

time: 1ms

memory: 3572kb

input:

1982 13

output:

result:

points 0.26173733120

Test #58:

score: 0.788187

Acceptable Answer

time: 1ms

memory: 3816kb

input:

1989 13

output:

result:

points 0.26272889710

Test #59:

score: 0.779482

Acceptable Answer

time: 0ms

memory: 3684kb

input:

1972 13

output:

result:

points 0.25982721530

Test #60:

score: 0.757421

Acceptable Answer

time: 1ms

memory: 3680kb

input:

1929 13

output:

result:

points 0.2524735810

Subtask #13:

score: 0.675207

Acceptable Answer

Test #61:

score: 0.676356

Acceptable Answer

time: 1ms

memory: 3920kb

input:

1979 14

output:

result:

points 0.22545205480

Test #62:

score: 0.676944

Acceptable Answer

time: 1ms

memory: 3596kb

input:

1980 14

output:

result:

points 0.22564816080

Test #63:

score: 0.675207

Acceptable Answer

time: 1ms

memory: 3684kb

input:

1987 14

output:

result:

points 0.22506890880

Test #64:

score: 0.684034

Acceptable Answer

time: 1ms

memory: 3916kb

input:

1952 14

output:

result:

points 0.22801120110

Test #65:

score: 0.686466

Acceptable Answer

time: 1ms

memory: 3684kb

input:

1936 14

output:

result:

points 0.22882209250

Subtask #14:

score: 0.935499

Acceptable Answer

Test #66:

score: 0.936009

Acceptable Answer

time: 1ms

memory: 3704kb

input:

2000 15

output:

result:

points 0.31200287770

Test #67:

score: 0.935499

Acceptable Answer

time: 1ms

memory: 3592kb

input:

1999 15

output:

result:

points 0.31183300790

Test #68:

score: 0.939628

Acceptable Answer

time: 1ms

memory: 3632kb

input:

1992 15

output:

result:

points 0.31320927890

Test #69:

score: 0.939857

Acceptable Answer

time: 1ms

memory: 3680kb

input:

1973 15

output:

result:

points 0.3132856890

Test #70:

score: 0.94199

Acceptable Answer

time: 0ms

memory: 3704kb

input:

1936 15

output:

result:

points 0.31399674760