QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#133982	#3269. 末日魔法少女计划	zhouhuanyi	58.149572	6ms	5896kb	C++23	3.2kb	2023-08-02 19:30:11	2023-08-02 19:30: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 19:30:14]
评测

测评结果：58.149572
用时：6ms
内存：5896kb

查看

[2023-08-02 19:30:11]
提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#define N 100000
#define SN 5000
#define M 3
#define inf 1e9
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],F[SN+1],F2[SN+1],ps[M+1][SN+1],dp[M+1][SN+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<=k) return;
	int res=r-l+1;
	vector<int>s(n+1);
	vector<int>used(n+1);
	vector<int>p(k);
	for (int i=k;i>=1;--i)
	{
		res=ps[i][res];
		if (i!=1) p[i-1]=res+l,s[p[i-1]]=used[p[i-1]]=1;
	}
	for (int i=l;i<=r;++i) s[i]+=s[i-1];
	for (int i=1;i<=k-2;++i)
		if (p[i+1]-p[i]>1)
			adder(p[i],p[i+1]);
	for (int i=l;i<=r;++i)
		if (!used[i])
		{
			if (s[i]&&i-p[s[i]]>1) adder(p[s[i]],i);
			if (s[i]!=k-1&&p[s[i]+1]-i>1) adder(i,p[s[i]+1]);
		}
	if (l<=p[1]-1) solve2(l,p[1]-1);
	for (int i=1;i<=k-2;++i)
		if (p[i]+1<=p[i+1]-1)
			solve2(p[i]+1,p[i+1]-1);
	if (p[k-1]+1<=r) solve2(p[k-1]+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<=k;++i)
			for (int j=0;j<=n;++j)
				dp[i][j]=inf;
		for (int i=1;i<=n;++i) F[i]=i-1,F2[i]=(i-1)<<1;
		for (int i=1;i<=n;++i)
		{
			if (i<=k+1) dp[1][i]=0;
			else
			{
				for (int j=2;j<=k;++j)
				{
					if (j==2)
					{
						for (int t=0;t<=i-1;++t)
							if (dp[j-1][t]+dp[1][i-1-t]+F[t]+F2[i-1-t]<dp[j][i])
								dp[j][i]=dp[j-1][t]+dp[1][i-1-t]+F[t]+F2[i-1-t],ps[j][i]=t;
					}
					else if (j==k)
					{
						for (int t=0;t<=i-1;++t)
							if (dp[j-1][t]+dp[1][i-1-t]+F[i-1-t]+(t!=i-1)<dp[j][i])
								dp[j][i]=dp[j-1][t]+dp[1][i-1-t]+F[i-1-t]+(t!=i-1),ps[j][i]=t;
					}
					else
					{
						for (int t=0;t<=i-1;++t)
							if (dp[j-1][t]+dp[1][i-1-t]+F2[i-1-t]+(t!=i-1)<dp[j][i])
								dp[j][i]=dp[j-1][t]+dp[1][i-1-t]+F2[i-1-t]+(t!=i-1),ps[j][i]=t;
					}
				}
				dp[1][i]=dp[k][i];
			}
		}
		solve2(1,n);
	}
	else
	{
		sz=k+2,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: 3780kb

input:

2000 2

output:

result:

ok

Test #2:

score: 22

Accepted

time: 3ms

memory: 3824kb

input:

1999 2

output:

result:

ok

Test #3:

score: 22

Accepted

time: 3ms

memory: 3844kb

input:

1992 2

output:

result:

ok

Test #4:

score: 22

Accepted

time: 3ms

memory: 3776kb

input:

1973 2

output:

result:

ok

Test #5:

score: 22

Accepted

time: 2ms

memory: 3776kb

input:

1936 2

output:

result:

ok

Subtask #2:

score: 2.98052

Acceptable Answer

Test #6:

score: 3.04494

Acceptable Answer

time: 5ms

memory: 4052kb

input:

1936 3

output:

result:

points 0.21749538370

Test #7:

score: 2.98052

Acceptable Answer

time: 3ms

memory: 4044kb

input:

2000 3

output:

result:

points 0.21289438440

Test #8:

score: 2.98149

Acceptable Answer

time: 3ms

memory: 4000kb

input:

1999 3

output:

result:

points 0.21296380890

Test #9:

score: 2.98833

Acceptable Answer

time: 6ms

memory: 5896kb

input:

1992 3

output:

result:

points 0.21345190490

Test #10:

score: 3.00714

Acceptable Answer

time: 6ms

memory: 3940kb

input:

1973 3

output:

result:

points 0.214795760

Subtask #3:

score: 9.98979

Acceptable Answer

Test #11:

score: 9.995

Acceptable Answer

time: 2ms

memory: 3752kb

input:

2000 4

output:

result:

points 0.90863673930

Test #12:

score: 9.98979

Acceptable Answer

time: 2ms

memory: 3824kb

input:

1999 4

output:

result:

points 0.90816264270

Test #13:

score: 10.0502

Acceptable Answer

time: 2ms

memory: 3760kb

input:

1991 4

output:

result:

points 0.9136571730

Test #14:

score: 10.1018

Acceptable Answer

time: 2ms

memory: 3752kb

input:

1971 4

output:

result:

points 0.91834961580

Test #15:

score: 10.184

Acceptable Answer

time: 0ms

memory: 3728kb

input:

1938 4

output:

result:

points 0.92581909010

Subtask #4:

score: 5.15103

Acceptable Answer

Test #16:

score: 5.15188

Acceptable Answer

time: 2ms

memory: 3744kb

input:

2000 5

output:

result:

points 0.57243142030

Test #17:

score: 5.15103

Acceptable Answer

time: 2ms

memory: 3732kb

input:

1999 5

output:

result:

points 0.57233611950

Test #18:

score: 5.15578

Acceptable Answer

time: 2ms

memory: 3804kb

input:

1992 5

output:

result:

points 0.57286391840

Test #19:

score: 5.17199

Acceptable Answer

time: 2ms

memory: 3796kb

input:

1973 5

output:

result:

points 0.57466586450

Test #20:

score: 5.19524

Acceptable Answer

time: 1ms

memory: 3844kb

input:

1936 5

output:

result:

points 0.57724891310

Subtask #5:

score: 2.56455

Acceptable Answer

Test #21:

score: 2.56455

Acceptable Answer

time: 0ms

memory: 3724kb

input:

2000 6

output:

result:

points 0.36636451260

Test #22:

score: 2.57014

Acceptable Answer

time: 2ms

memory: 5812kb

input:

1997 6

output:

result:

points 0.36716329250

Test #23:

score: 2.57188

Acceptable Answer

time: 2ms

memory: 3724kb

input:

1989 6

output:

result:

points 0.36741085370

Test #24:

score: 2.57495

Acceptable Answer

time: 2ms

memory: 3724kb

input:

1972 6

output:

result:

points 0.36785028690

Test #25:

score: 2.59337

Acceptable Answer

time: 2ms

memory: 3736kb

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

input:

1999 7

output:

result:

points 0.41397901850

Test #27:

score: 2.48052

Acceptable Answer

time: 2ms

memory: 3736kb

input:

1997 7

output:

result:

points 0.41342003780

Test #28:

score: 2.48494

Acceptable Answer

time: 2ms

memory: 3728kb

input:

1987 7

output:

result:

points 0.41415663210

Test #29:

score: 2.4911

Acceptable Answer

time: 0ms

memory: 3704kb

input:

1978 7

output:

result:

points 0.41518397560

Test #30:

score: 2.50844

Acceptable Answer

time: 2ms

memory: 3716kb

input:

1931 7

output:

result:

points 0.4180729170

Subtask #7:

score: 1.84948

Acceptable Answer

Test #31:

score: 1.85423

Acceptable Answer

time: 1ms

memory: 3788kb

input:

1995 8

output:

result:

points 0.37084653480

Test #32:

score: 1.84948

Acceptable Answer

time: 1ms

memory: 3744kb

input:

1999 8

output:

result:

points 0.36989663260

Test #33:

score: 1.85423

Acceptable Answer

time: 2ms

memory: 3724kb

input:

1987 8

output:

result:

points 0.37084557550

Test #34:

score: 1.85662

Acceptable Answer

time: 0ms

memory: 3784kb

input:

1981 8

output:

result:

points 0.37132490180

Test #35:

score: 1.88399

Acceptable Answer

time: 2ms

memory: 3784kb

input:

1923 8

output:

result:

points 0.37679787060

Subtask #8:

score: 2.07348

Acceptable Answer

Test #36:

score: 2.07348

Acceptable Answer

time: 1ms

memory: 3740kb

input:

1997 9

output:

result:

points 0.41469539130

Test #37:

score: 2.07456

Acceptable Answer

time: 1ms

memory: 3720kb

input:

1998 9

output:

result:

points 0.41491256870

Test #38:

score: 2.0766

Acceptable Answer

time: 1ms

memory: 3784kb

input:

1990 9

output:

result:

points 0.41531960960

Test #39:

score: 2.08182

Acceptable Answer

time: 0ms

memory: 3716kb

input:

1975 9

output:

result:

points 0.41636397520

Test #40:

score: 2.10251

Acceptable Answer

time: 1ms

memory: 3740kb

input:

1934 9

output:

result:

points 0.42050174410

Subtask #9:

score: 1.57605

Acceptable Answer

Test #41:

score: 1.57605

Acceptable Answer

time: 2ms

memory: 5692kb

input:

1995 10

output:

result:

points 0.3940133850

Test #42:

score: 1.57681

Acceptable Answer

time: 1ms

memory: 3732kb

input:

1996 10

output:

result:

points 0.39420262370

Test #43:

score: 1.57901

Acceptable Answer

time: 0ms

memory: 3780kb

input:

1979 10

output:

result:

points 0.39475246390

Test #44:

score: 1.58127

Acceptable Answer

time: 1ms

memory: 3728kb

input:

1972 10

output:

result:

points 0.39531817670

Test #45:

score: 1.58353

Acceptable Answer

time: 2ms

memory: 3788kb

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

input:

1993 11

output:

result:

points 0.41766843470

Test #47:

score: 1.67137

Acceptable Answer

time: 1ms

memory: 3836kb

input:

1994 11

output:

result:

points 0.41784283990

Test #48:

score: 1.66752

Acceptable Answer

time: 1ms

memory: 3736kb

input:

2000 11

output:

result:

points 0.41688078040

Test #49:

score: 1.67213

Acceptable Answer

time: 0ms

memory: 3800kb

input:

1972 11

output:

result:

points 0.41803303430

Test #50:

score: 1.67688

Acceptable Answer

time: 1ms

memory: 3784kb

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

input:

1999 12

output:

result:

points 0.42444798660

Test #52:

score: 1.69004

Acceptable Answer

time: 2ms

memory: 3724kb

input:

2000 12

output:

result:

points 0.42251022370

Test #53:

score: 1.69987

Acceptable Answer

time: 2ms

memory: 3788kb

input:

1989 12

output:

result:

points 0.42496673240

Test #54:

score: 1.70004

Acceptable Answer

time: 1ms

memory: 3840kb

input:

1976 12

output:

result:

points 0.42501121650

Test #55:

score: 1.7084

Acceptable Answer

time: 0ms

memory: 3732kb

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

input:

1981 13

output:

result:

points 0.43709860820

Test #57:

score: 1.31174

Acceptable Answer

time: 1ms

memory: 3736kb

input:

1982 13

output:

result:

points 0.4372459450

Test #58:

score: 1.31482

Acceptable Answer

time: 1ms

memory: 3840kb

input:

1989 13

output:

result:

points 0.43827422850

Test #59:

score: 1.31398

Acceptable Answer

time: 1ms

memory: 3832kb

input:

1972 13

output:

result:

points 0.43799219860

Test #60:

score: 1.32184

Acceptable Answer

time: 0ms

memory: 3720kb

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

input:

1979 14

output:

result:

points 0.46089328330

Test #62:

score: 1.37609

Acceptable Answer

time: 1ms

memory: 3784kb

input:

1980 14

output:

result:

points 0.45869603740

Test #63:

score: 1.37897

Acceptable Answer

time: 1ms

memory: 3720kb

input:

1987 14

output:

result:

points 0.45965524060

Test #64:

score: 1.38567

Acceptable Answer

time: 1ms

memory: 3800kb

input:

1952 14

output:

result:

points 0.46189075520

Test #65:

score: 1.38616

Acceptable Answer

time: 1ms

memory: 3716kb

input:

1936 14

output:

result:

points 0.46205183180

Subtask #14:

score: 1.4392

Acceptable Answer

Test #66:

score: 1.44226

Acceptable Answer

time: 1ms

memory: 3712kb

input:

2000 15

output:

result:

points 0.48075275040

Test #67:

score: 1.44188

Acceptable Answer

time: 1ms

memory: 3720kb

input:

1999 15

output:

result:

points 0.48062579680

Test #68:

score: 1.4392

Acceptable Answer

time: 0ms

memory: 3776kb

input:

1992 15

output:

result:

points 0.4797344270

Test #69:

score: 1.44657

Acceptable Answer

time: 1ms

memory: 3784kb

input:

1973 15

output:

result:

points 0.48219141220

Test #70:

score: 1.45467

Acceptable Answer

time: 1ms

memory: 3728kb

input:

1936 15

output:

result:

points 0.48488838710