QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#744130	#3269. 末日魔法少女计划	TheZone	100 ✓	80ms	4708kb	C++20	4.1kb	2024-11-13 20:57:06	2024-11-13 20:57:12

Judging History

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

[2024-11-13 20:57:12]
评测

测评结果：100
用时：80ms
内存：4708kb

查看

[2024-11-13 20:57:06]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int f[16][2005],g[16][2005],fx[16][2005],gx[16][2005];
int eval(int k,int n,int o) {
	//o=1:pre, o=2:suf, o=3:pre&suf
	if(n<=1) return 0;
	if(o==1) return n-1+f[k][n-1];
	if(o==2) return n-1+f[k][n-1];
	if(o==3) return 2*n-3+f[k][n-2];
	return f[k][n];
}
struct info { int l,r; };
vector <info> e;
void link(info u,info v) { e.push_back({u.l,v.r}); }
void sol(vector<info>q,int k,int o) {
	#define sc(x,y) {q.begin()+x,q.begin()+y}
	int n=q.size();
	if(n<=1) return ;
	if(o==1) {
		for(int i=1;i<n;++i) link(q[0],q[i]);
		return sol(sc(1,n),k,0);
	}
	if(o==2) {
		for(int i=0;i<n-1;++i) link(q[i],q[n-1]);
		return sol(sc(0,n-1),k,0);
	}
	if(o==3) {
		for(int i=1;i<n-1;++i) link(q[0],q[i]),link(q[i],q[n-1]);
		return link(q[0],q[n-1]),sol(sc(1,n-1),k,0);
	}
	if(n<=k) return ;
	else if(k==1) for(int i=0;i<n;++i) for(int j=i+1;j<n;++j) link(q[i],q[j]);
	else if(k==2) sol(sc(0,n/2),k,2),sol(sc(n/2,n),k,1);
	else {
		int wd=fx[k][n];
		sol(sc(0,wd),k,2),sol(sc(n-wd,n),k,1);
		vector<info> s;
		int b=gx[k][n-2*wd],d=(n-2*wd)/b,r=(n-2*wd)%b,it=wd;
		for(int i=0;i<b-r;++i) sol(sc(it,it+d),k,3),s.push_back({q[it].l,q[it+d-1].r}),it+=d;
		for(int i=0;i<r;++i) sol(sc(it,it+d+1),k,3),s.push_back({q[it].l,q[it+d].r}),it+=d+1;
		sol(s,k-2,0);
	}
}
signed main() {
	for(int k=1;k<=15;++k) for(int n=2;n<=2000;++n) {
		g[k][n]=inf;
		for(int b=1;b<=n;++b) {
			int d=n/b,r=n%b,tmp=eval(k-2,b,0)+eval(k,d,3)*(b-r)+eval(k,d+1,3)*r;
			if(tmp<g[k][n]) g[k][n]=tmp,gx[k][n]=b;
		}
		if(n<=k) f[k][n]=0;
		else if(k==1) f[k][n]=n*(n-1)/2;
		else if(k==2) f[k][n]=eval(k,n/2,2)+eval(k,n-n/2,1);
		else {
			f[k][n]=inf;
			for(int i=1;i<=n/2;++i) {
				int tmp=g[k][n-2*i]+eval(k,i,2)+eval(k,i,1);
				if(tmp<f[k][n]) f[k][n]=tmp,fx[k][n]=i;
			}
		}
	}
	int N,K;
	scanf("%d%d",&N,&K);
	vector <info> I;
	for(int i=0;i<N;++i) I.push_back({i,i+1});
	sol(I,K,0);
	printf("%d\n",(int)e.size());
	for(auto x:e) printf("%d %d\n",x.l,x.r);
	return 0;
}
/*#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int f[16][2005],g[16][2005],fx[16][2005],gx[16][2005];
int eval(int k,int n,int o) {
	//o=1:pre, o=2:suf, o=3:pre&suf
	if(n<=1) return 0;
	if(o==1) return n-1+f[k][n-1];
	if(o==2) return n-1+f[k][n-1];
	if(o==3) return 2*n-3+f[k][n-2];
	return f[k][n];
}
struct info { int l,r; };
vector <info> e;
void link(info u,info v) { e.push_back({u.l,v.r}); }
void sol(vector<info>q,int k,int o) {
	#define sc(x,y) {q.begin()+x,q.begin()+y}
	int n=q.size();
	if(n<=1) return ;
	if(o==1) {
		for(int i=1;i<n;++i) link(q[0],q[i]);
		return sol(sc(1,n),k,0);
	}
	if(o==2) {
		for(int i=0;i<n-1;++i) link(q[i],q[n-1]);
		return sol(sc(0,n-1),k,0);
	}
	if(o==3) {
		for(int i=1;i<n-1;++i) link(q[0],q[i]),link(q[i],q[n-1]);
		return link(q[0],q[n-1]),sol(sc(1,n-1),k,0);
	}
	if(n<=k) return ;
	else if(k==1) for(int i=0;i<n;++i) for(int j=i+1;j<n;++j) link(q[i],q[j]);
	else if(k==2) sol(sc(0,n/2),k,2),sol(sc(n/2,n),k,1);
	else {
		int wd=fx[k][n];
		sol(sc(0,wd),k,2),sol(sc(n-wd,n),k,1);
		vector<info> s;
		int b=gx[k][n-2*wd],d=(n-2*wd)/b,r=(n-2*wd)%b,it=wd;
		for(int i=0;i<b-r;++i) sol(sc(it,it+d),k,3),s.push_back({q[it].l,q[it+d-1].r}),it+=d;
		for(int i=0;i<r;++i) sol(sc(it,it+d+1),k,3),s.push_back({q[it].l,q[it+d].r}),it+=d+1;
		sol(s,k-2,0);
	}
}
signed main() {
	for(int k=1;k<=15;++k) for(int n=2;n<=2000;++n) {
		g[k][n]=inf;
		for(int b=1;b<=n;++b) {
			int d=n/b,r=n%b,tmp=eval(k-2,b,0)+eval(k,d,3)*(b-r)+eval(k,d+1,3)*r;
			if(tmp<g[k][n]) g[k][n]=tmp,gx[k][n]=b;
		}
		if(n<=k) f[k][n]=0;
		else if(k==1) f[k][n]=n*(n-1)/2;
		else if(k==2) f[k][n]=eval(k,n/2,2)+eval(k,n-n/2,1);
		else {
			f[k][n]=inf;
			for(int i=1;i<=n/2;++i) {
				int tmp=g[k][n-2*i]+eval(k,i,2)+eval(k,i,1);
				if(tmp<f[k][n]) f[k][n]=tmp,fx[k][n]=i;
			}
		}
	}
	int N,K;
	scanf("%d%d",&N,&K);
	vector <info> I;
	for(int i=0;i<N;++i) I.push_back({i,i+1});
	sol(I,K,0);
	printf("%d\n",(int)e.size());
	for(auto x:e) printf("%d %d\n",x.l,x.r);
	return 0;
}*/

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 22

Accepted

Test #1:

score: 22

Accepted

time: 80ms

memory: 4444kb

input:

2000 2

output:

result:

ok

Test #2:

score: 22

Accepted

time: 76ms

memory: 4492kb

input:

1999 2

output:

result:

ok

Test #3:

score: 22

Accepted

time: 80ms

memory: 4424kb

input:

1992 2

output:

result:

ok

Test #4:

score: 22

Accepted

time: 74ms

memory: 4500kb

input:

1973 2

output:

result:

ok

Test #5:

score: 22

Accepted

time: 76ms

memory: 4708kb

input:

1936 2

output:

result:

ok

Subtask #2:

score: 14

Accepted

Test #6:

score: 14

Accepted

time: 79ms

memory: 4672kb

input:

1936 3

output:

result:

ok

Test #7:

score: 14

Accepted

time: 79ms

memory: 4388kb

input:

2000 3

output:

result:

ok

Test #8:

score: 14

Accepted

time: 79ms

memory: 4412kb

input:

1999 3

output:

result:

ok

Test #9:

score: 14

Accepted

time: 79ms

memory: 4372kb

input:

1992 3

output:

result:

ok

Test #10:

score: 14

Accepted

time: 79ms

memory: 4672kb

input:

1973 3

output:

result:

ok

Subtask #3:

score: 11

Accepted

Test #11:

score: 11

Accepted

time: 79ms

memory: 4480kb

input:

2000 4

output:

result:

ok

Test #12:

score: 11

Accepted

time: 80ms

memory: 4684kb

input:

1999 4

output:

result:

ok

Test #13:

score: 11

Accepted

time: 75ms

memory: 4416kb

input:

1991 4

output:

result:

ok

Test #14:

score: 11

Accepted

time: 72ms

memory: 4384kb

input:

1971 4

output:

result:

ok

Test #15:

score: 11

Accepted

time: 79ms

memory: 4412kb

input:

1938 4

output:

result:

ok

Subtask #4:

score: 9

Accepted

Test #16:

score: 9

Accepted

time: 79ms

memory: 4372kb

input:

2000 5

output:

result:

ok

Test #17:

score: 9

Accepted

time: 79ms

memory: 4284kb

input:

1999 5

output:

result:

ok

Test #18:

score: 9

Accepted

time: 75ms

memory: 4368kb

input:

1992 5

output:

result:

ok

Test #19:

score: 9

Accepted

time: 79ms

memory: 4356kb

input:

1973 5

output:

result:

ok

Test #20:

score: 9

Accepted

time: 80ms

memory: 4380kb

input:

1936 5

output:

result:

ok

Subtask #5:

score: 7

Accepted

Test #21:

score: 7

Accepted

time: 79ms

memory: 4364kb

input:

2000 6

output:

result:

ok

Test #22:

score: 7

Accepted

time: 79ms

memory: 4352kb

input:

1997 6

output:

result:

ok

Test #23:

score: 7

Accepted

time: 79ms

memory: 4384kb

input:

1989 6

output:

result:

ok

Test #24:

score: 7

Accepted

time: 79ms

memory: 4612kb

input:

1972 6

output:

result:

ok

Test #25:

score: 7

Accepted

time: 78ms

memory: 4356kb

input:

1933 6

output:

result:

ok

Subtask #6:

score: 6

Accepted

Test #26:

score: 6

Accepted

time: 79ms

memory: 4452kb

input:

1999 7

output:

result:

ok

Test #27:

score: 6

Accepted

time: 79ms

memory: 4348kb

input:

1997 7

output:

result:

ok

Test #28:

score: 6

Accepted

time: 79ms

memory: 4644kb

input:

1987 7

output:

result:

ok

Test #29:

score: 6

Accepted

time: 75ms

memory: 4660kb

input:

1978 7

output:

result:

ok

Test #30:

score: 6

Accepted

time: 79ms

memory: 4352kb

input:

1931 7

output:

result:

ok

Subtask #7:

score: 5

Accepted

Test #31:

score: 5

Accepted

time: 79ms

memory: 4380kb

input:

1995 8

output:

result:

ok

Test #32:

score: 5

Accepted

time: 79ms

memory: 4372kb

input:

1999 8

output:

result:

ok

Test #33:

score: 5

Accepted

time: 79ms

memory: 4344kb

input:

1987 8

output:

result:

ok

Test #34:

score: 5

Accepted

time: 79ms

memory: 4348kb

input:

1981 8

output:

result:

ok

Test #35:

score: 5

Accepted

time: 79ms

memory: 4376kb

input:

1923 8

output:

result:

ok

Subtask #8:

score: 5

Accepted

Test #36:

score: 5

Accepted

time: 79ms

memory: 4336kb

input:

1997 9

output:

result:

ok

Test #37:

score: 5

Accepted

time: 79ms

memory: 4600kb

input:

1998 9

output:

result:

ok

Test #38:

score: 5

Accepted

time: 80ms

memory: 4376kb

input:

1990 9

output:

result:

ok

Test #39:

score: 5

Accepted

time: 79ms

memory: 4344kb

input:

1975 9

output:

result:

ok

Test #40:

score: 5

Accepted

time: 79ms

memory: 4644kb

input:

1934 9

output:

result:

ok

Subtask #9:

score: 4

Accepted

Test #41:

score: 4

Accepted

time: 79ms

memory: 4376kb

input:

1995 10

output:

result:

ok

Test #42:

score: 4

Accepted

time: 75ms

memory: 4428kb

input:

1996 10

output:

result:

ok

Test #43:

score: 4

Accepted

time: 79ms

memory: 4356kb

input:

1979 10

output:

result:

ok

Test #44:

score: 4

Accepted

time: 79ms

memory: 4296kb

input:

1972 10

output:

result:

ok

Test #45:

score: 4

Accepted

time: 79ms

memory: 4628kb

input:

1945 10

output:

result:

ok

Subtask #10:

score: 4

Accepted

Test #46:

score: 4

Accepted

time: 80ms

memory: 4644kb

input:

1993 11

output:

result:

ok

Test #47:

score: 4

Accepted

time: 75ms

memory: 4364kb

input:

1994 11

output:

result:

ok

Test #48:

score: 4

Accepted

time: 80ms

memory: 4436kb

input:

2000 11

output:

result:

ok

Test #49:

score: 4

Accepted

time: 79ms

memory: 4372kb

input:

1972 11

output:

result:

ok

Test #50:

score: 4

Accepted

time: 75ms

memory: 4436kb

input:

1944 11

output:

result:

ok

Subtask #11:

score: 4

Accepted

Test #51:

score: 4

Accepted

time: 79ms

memory: 4444kb

input:

1999 12

output:

result:

ok

Test #52:

score: 4

Accepted

time: 79ms

memory: 4368kb

input:

2000 12

output:

result:

ok

Test #53:

score: 4

Accepted

time: 75ms

memory: 4352kb

input:

1989 12

output:

result:

ok

Test #54:

score: 4

Accepted

time: 78ms

memory: 4328kb

input:

1976 12

output:

result:

ok

Test #55:

score: 4

Accepted

time: 79ms

memory: 4624kb

input:

1949 12

output:

result:

ok

Subtask #12:

score: 3

Accepted

Test #56:

score: 3

Accepted

time: 79ms

memory: 4628kb

input:

1981 13

output:

result:

ok

Test #57:

score: 3

Accepted

time: 79ms

memory: 4616kb

input:

1982 13

output:

result:

ok

Test #58:

score: 3

Accepted

time: 79ms

memory: 4324kb

input:

1989 13

output:

result:

ok

Test #59:

score: 3

Accepted

time: 79ms

memory: 4352kb

input:

1972 13

output:

result:

ok

Test #60:

score: 3

Accepted

time: 80ms

memory: 4408kb

input:

1929 13

output:

result:

ok

Subtask #13:

score: 3

Accepted

Test #61:

score: 3

Accepted

time: 79ms

memory: 4352kb

input:

1979 14

output:

result:

ok

Test #62:

score: 3

Accepted

time: 79ms

memory: 4332kb

input:

1980 14

output:

result:

ok

Test #63:

score: 3

Accepted

time: 79ms

memory: 4408kb

input:

1987 14

output:

result:

ok

Test #64:

score: 3

Accepted

time: 79ms

memory: 4624kb

input:

1952 14

output:

result:

ok

Test #65:

score: 3

Accepted

time: 79ms

memory: 4344kb

input:

1936 14

output:

result:

ok

Subtask #14:

score: 3

Accepted

Test #66:

score: 3

Accepted

time: 79ms

memory: 4352kb

input:

2000 15

output:

result:

ok

Test #67:

score: 3

Accepted

time: 79ms

memory: 4352kb

input:

1999 15

output:

result:

ok

Test #68:

score: 3

Accepted

time: 78ms

memory: 4420kb

input:

1992 15

output:

result:

ok

Test #69:

score: 3

Accepted

time: 79ms

memory: 4352kb

input:

1973 15

output:

result:

ok

Test #70:

score: 3

Accepted

time: 78ms

memory: 4612kb

input:

1936 15

output:

result:

ok