QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#430536#8349. 零和Kevin5307100 ✓790ms14040kbC++236.8kb2024-06-03 22:00:342024-06-03 22:00:34

Judging History

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

  • [2024-06-03 22:00:34]
  • 评测
  • 测评结果：100
  • 用时：790ms
  • 内存：14040kb
查看
  • [2024-06-03 22:00:34]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const int thres=1000000;
int dist[1001000];
int lst[1001000];
ll val[31][31];
ll val2[31][31];
bool flag[1001000];
ll val3[31][31][31],val4[31][31][31];
ll val5[31][31][31],val6[31][31][31];
vector<ll> solve(int k)
{
	if(k==1) return vector<ll>();
	if(k==2) return vector<ll>({1,-1});
	if(lst[k]==-1)
	{
		vector<ll> vec=solve(k-1);
		ll sum=0;
		for(auto x:vec)
			if(x>0)
				sum+=x;
		if(!sum)
		{
			vector<ll> nvec;
			int xx=1;
			for(auto x:vec)
			{
				nvec.pb(xx);
				nvec.pb(-xx);
				xx*=2;
			}
			swap(vec,nvec);
			for(auto x:vec)
				if(x>0)
					sum+=x;
		}
		vec.pb(-sum);
		return vec;
	}
	if(lst[k]<0)
	{
		int l=-lst[k];
		if(l<1000000)
		{
			int i=l/10000,j=l%10000;
			vector<ll> v1=solve((k-val2[i][j])/val[i][j]);
			ll sum=0,sum2=0;
			for(auto x:v1)
				if(x>0)
					sum+=x;
				else
					sum2+=-x;
			if(sum2>sum)
			{
				swap(i,j);
				sum=sum2;
			}
			while(i--)
				v1.pb(sum);
			while(j--)
				v1.pb(-sum);
			return v1;
		}
		else
		{
			int i=l/1000000,j=l/1000%1000,kk=l%1000;
			vector<ll> v1=solve((k-val4[i][j][kk])/val3[i][j][kk]);
			ll sum=0,sum2=0;
			for(auto x:v1)
				if(x>0)
					sum+=x;
				else
					sum2+=-x;
			if(sum2>sum)
			{
				for(auto &x:v1)
					x*=-1;
				sum=sum2;
			}
			while(i--)
				v1.pb(sum);
			while(j--)
				v1.pb(-sum);
			while(kk--)
				v1.pb(-sum-sum);
			return v1;
		}
	}
	if(lst[k]<100000000&&lst[k]>1000000)
	{
		int i=lst[k]/1000000;
		int j=lst[k]%1000000;
		vector<ll> tmp;
		while(i--)
			tmp.pb(1);
		while(j--)
			tmp.pb(-1);
		return tmp;
	}
	if(lst[k]>=100000000)
	{
		int l=lst[k];
		int i=l/100000000,j=l/10000%10000,kk=l%10000;
		vector<ll> v1=solve((k-val6[i][j][kk])/val5[i][j][kk]);
		ll sum=0,sum2=0;
		for(auto x:v1)
			if(x>0)
				sum+=x;
			else
				sum2+=-x;
		if(sum2>sum)
		{
			for(auto &x:v1)
				x*=-1;
			sum=sum2;
		}
		while(i--)
			v1.pb(sum);
		while(j--)
			v1.pb(-sum);
		while(kk--)
			v1.pb(sum+sum);
		return v1;
	}
	vector<ll> v1=solve(lst[k]),v2=solve(k/lst[k]);
	ll sum=0;
	for(auto x:v1)
		sum+=abs(x);
	for(auto x:v2)
		v1.pb((sum+1)*x);
	return v1;
}
ll C[31][31];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	for(int i=0;i<=30;i++)
		C[i][i]=C[i][0]=1;
	for(int i=2;i<=30;i++)
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1]);
	memset(dist,inf,sizeof(dist));
	dist[1]=0;
	dist[2]=2;
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.emplace(0,1);
	pq.emplace(2,2);
	for(int i=1;i<=30;i++)
		for(int j=1;j<=30-i;j++)
		{
			ll sum=0;
			for(int x=0;x<=min(i,j);x++)
			{
				sum+=1ll*C[i][x]*C[j][x];
				// cerr<<i<<" "<<j<<" "<<x<<" "<<C[i][x]<<" "<<C[j][x]<<endl;
			}
			// cerr<<i<<" "<<j<<" "<<sum<<endl;
			val[i][j]=sum;
			for(int x=0;x<=min(i,j);x++)
				val2[i][j]+=1ll*C[i][x]*C[j][x+1];
			if(sum<=thres&&dist[sum]>i+j)
			{
				dist[sum]=i+j;
				lst[sum]=i*1000000+j;
				flag[sum]=(i!=j);
				pq.emplace(i+j,sum);
			}
		}
	for(int i=1;i<=30;i++)
		for(int j=1;j<=30-i;j++)
			for(int k=1;k<=30-i-j;k++)
			{
				ll sum=0;
				for(int a=0;a<=i;a++)
					for(int b=0;b<=j;b++)
						for(int c=0;c<=k;c++)
							if(a==b+c+c)
								sum=sum+1ll*C[i][a]*C[j][b]*C[k][c];
				val3[i][j][k]=sum;
				sum=0;
				for(int a=0;a<=i;a++)
					for(int b=0;b<=j;b++)
						for(int c=0;c<=k;c++)
							if(a+1==b+c+c)
								sum=sum+1ll*C[i][a]*C[j][b]*C[k][c];
				val4[i][j][k]=sum;
			}
	for(int i=1;i<=30;i++)
		for(int j=1;j<=30-i;j++)
			for(int k=1;k<=30-i-j;k++)
			{
				ll sum=0;
				for(int a=0;a<=i;a++)
					for(int b=0;b<=j;b++)
						for(int c=0;c<=k;c++)
							if(a+c+c==b)
								sum=sum+1ll*C[i][a]*C[j][b]*C[k][c];
				val5[i][j][k]=sum;
				sum=0;
				for(int a=0;a<=i;a++)
					for(int b=0;b<=j;b++)
						for(int c=0;c<=k;c++)
							if(a+c+c+1==b)
								sum=sum+1ll*C[i][a]*C[j][b]*C[k][c];
				val6[i][j][k]=sum;
			}
	for(int x=1;x<=thres;x++)
	{
		// int x=pq.top().second;
		// int d=pq.top().first;
		// pq.pop();
		// if(dist[x]!=d) continue;
		int d=dist[x];
		if(flag[x])
		{
			for(int i=1;i<=30;i++)
				for(int j=1;j<=30-i;j++)
				{
					ll sum=val[i][j];
					ll nx=sum*x+val2[i][j];
					if(nx<=thres&&dist[nx]>i+j+d)
					{
						dist[nx]=i+j+d;
						lst[nx]=-10000*i-j;
						flag[nx]=abs(i-j)!=1;
						// pq.emplace(i+j+d,nx);
					}
				}
			if(x<=140000)
			{
				int lim=(x<10000?30:20);
				for(int i=1;i<=lim;i++)
					for(int j=1;j<=lim-i;j++)
						for(int k=1;k<=lim-i-j;k++)
						{
							ll sum=val3[i][j][k];
							if(sum>thres) continue;
							ll nx=sum*x+val4[i][j][k];
							if(nx<=thres&&dist[nx]>i+j+k+d)
							{
								dist[nx]=i+j+k+d;
								lst[nx]=-1000000*i-1000*j-k;
								flag[nx]=abs(i-j-k-k)!=1;
								// pq.emplace(i+j+d,nx);
							}
						}
				if(x<=100000)
					for(int i=1;i<=lim;i++)
						for(int j=1;j<=lim-i;j++)
							for(int k=1;k<=lim-i-j;k++)
							{
								ll sum=val5[i][j][k];
								if(sum>thres) continue;
								ll nx=sum*x+val6[i][j][k];
								if(nx<=thres&&dist[nx]>i+j+k+d)
								{
									dist[nx]=i+j+k+d;
									lst[nx]=100000000*i+10000*j+k;
									flag[nx]=abs(j-i-k-k)!=1;
									// pq.emplace(i+j+d,nx);
								}
							}
			}
		}
		if(x>1&&x+1<=thres&&dist[x+1]>d+1)
		{
			dist[x+1]=d+1;
			lst[x+1]=-1;
			flag[x+1]=1;
			pq.emplace(d+1,x+1);
		}
		for(int j=1;j<=thres/x;j++)
			if(dist[j]+dist[x]<dist[x*j])
			{
				dist[x*j]=dist[j]+dist[x];
				lst[x*j]=j;
				flag[x*j]=flag[x];
				// pq.emplace(dist[x*j],x*j);
			}
	}
	for(int i=1;i<=thres;i++)
		for(int j=1;j<=thres/i;j++)
		{
			if(dist[i*j]>dist[i]+dist[j])
				lst[i*j]=i;
			dist[i*j]=min(dist[i*j],dist[i]+dist[j]);
		}
	for(int i=1;i<=thres;i++)
		if(i+i<=thres)
			dist[i+i]=min(dist[i+i],dist[i]+1);
	// for(int i=1;i<=thres;i++)
	// 	if(dist[i]>30)
	// 	{
	// 		cout<<i<<" "<<dist[i]<<endl;
	// 		// assert(dist[i]<=32);
	// 		// return 0;
	// 	}
	int t;
	cin>>t;
	while(t--)
	{
		int k;
		cin>>k;
		vector<ll> vec=solve(k);
		if(!sz(vec)) vec.pb(1);
		cout<<sz(vec)<<'\n';
		for(auto x:vec)
			cout<<x<<" ";
		cout<<'\n';
	}
	return 0;
}
源文件, 语言: C++23

详细

Subtask #1:

score: 15
Accepted

Test #1:

score: 15
Accepted
time: 787ms
memory: 13800kb

input:

1000
4
10
9
7
5
9
4
4
10
8
2
10
8
8
4
2
10
4
9
9
8
9
6
9
5
6
9
1
2
5
8
4
4
8
2
2
7
6
8
2
3
1
1
3
1
10
6
3
4
1
6
7
1
5
7
7
3
6
3
3
9
6
9
5
7
5
9
8
3
5
2
4
9
3
10
2
10
10
3
1
9
4
8
9
6
6
6
7
7
7
10
1
2
3
2
6
6
8
1
3
10
8
5
7
8
2
7
9
3
1
9
9
1
10
6
7
9
9
7
9
1
2
7
3
1
5
4
9
2
6
4
9
9
10
4
4
5
9
10
2
2
...

output:

4
1 -1 -1 -1 
5
1 1 -1 -1 -1 
6
1 -1 -1 4 -4 -4 
5
1 -1 -1 2 -2 
5
1 -1 -1 -1 -1 
6
1 -1 -1 4 -4 -4 
4
1 -1 -1 -1 
4
1 -1 -1 -1 
5
1 1 -1 -1 -1 
6
1 -1 -1 -1 5 -5 
2
1 -1 
5
1 1 -1 -1 -1 
6
1 -1 -1 -1 5 -5 
6
1 -1 -1 -1 5 -5 
4
1 -1 -1 -1 
2
1 -1 
5
1 1 -1 -1 -1 
4
1 -1 -1 -1 
6
1 -1 -1 4 -4 -4 
6
1...

result:

ok Accepted

Subtask #2:

score: 15
Accepted

Dependency #1:

100%
Accepted

Test #2:

score: 15
Accepted
time: 782ms
memory: 13844kb

input:

1000
42
56
95
81
26
68
42
3
83
6
37
52
5
82
59
10
43
90
44
55
83
8
43
14
94
84
92
61
10
98
46
58
43
49
81
29
36
3
93
38
70
86
54
89
75
28
87
74
56
22
47
89
90
26
76
80
55
90
60
32
58
67
70
94
52
95
78
70
39
40
69
99
18
24
32
33
23
95
19
80
98
59
79
57
69
35
25
72
27
72
57
13
55
37
90
59
53
10
2
84
4...

output:

9
1 1 -1 -1 -1 -1 -1 8 -8 
8
1 1 1 -1 -1 -1 -1 -1 
10
1 -1 -1 -1 3 3 3 -3 -3 -3 
11
1 -1 -1 -1 -1 4 4 -4 -4 -4 -4 
9
-1 1 1 2 -2 -2 -2 -2 -4 
11
-1 1 1 1 3 3 -3 -3 -3 -6 -6 
9
1 1 -1 -1 -1 -1 -1 8 -8 
3
1 -1 -1 
11
-1 1 1 2 2 -2 -2 -2 -2 -4 -4 
4
1 1 -1 -1 
9
1 -1 -1 2 2 2 -2 7 -7 
10
1 -1 -1 2 2 -2...

result:

ok Accepted

Subtask #3:

score: 15
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #3:

score: 15
Accepted
time: 788ms
memory: 13580kb

input:

1000
1458
1427
1927
1845
764
1218
986
13
1479
494
1405
1711
88
1701
536
1286
1735
711
63
439
469
1726
739
1496
1055
1775
1946
860
134
742
1296
188
373
1156
230
1366
1123
1601
1015
481
1177
250
723
1265
1254
416
329
489
661
305
1895
1057
1676
676
1972
1031
1721
1483
1046
387
1522
1936
1778
1526
27
11...

output:

16
-1 1 1 2 2 2 -2 -4 8 8 -8 -8 -8 -8 16 16 
17
-1 -1 1 1 1 2 5 5 5 5 -5 -5 -10 25 -25 -25 50 
17
1 -1 -1 4 4 4 -4 -4 -4 -4 16 16 -16 -16 50 -50 -50 
16
1 1 -1 -1 -1 -1 4 4 4 -4 -4 -4 -4 -4 -4 -4 
13
-1 1 1 2 2 2 2 2 2 -2 -2 -4 -4 
14
1 -1 -1 -1 3 3 3 3 3 -3 -3 -3 -3 -3 
15
1 -1 -1 2 2 2 2 -2 -2 9 9...

result:

ok Accepted

Subtask #4:

score: 15
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #4:

score: 15
Accepted
time: 789ms
memory: 13588kb

input:

1000
8882
3890
5276
2293
7017
8729
4107
8330
9804
3437
7125
8266
505
902
10
4246
46
4186
7869
6510
3510
681
8065
2419
1575
2776
2762
5567
3150
5914
4695
6152
2758
5157
1407
5964
8947
8203
7821
3411
3115
8356
8240
3506
1618
1108
4024
5791
2644
3315
3577
9512
5256
3454
7378
9383
4904
6094
8422
7100
71...

output:

19
1 -1 3 3 -3 -3 -3 9 9 9 9 -9 -9 -9 -9 -9 -9 63 -63 
18
-1 1 1 -2 2 4 4 4 4 -4 -4 -4 -4 -4 -4 -4 -8 -8 
19
1 1 1 -1 -1 -1 -1 -1 -5 5 10 18 18 -18 -18 -18 -18 36 36 
16
-1 -1 1 1 1 3 3 3 3 -3 -3 -3 -3 -3 -6 -6 
19
-1 -1 -1 1 1 1 1 4 4 4 -4 -4 -4 -4 -4 -8 31 31 -31 
20
1 1 1 -1 -1 -1 -1 4 4 4 4 -4 -...

result:

ok Accepted

Subtask #5:

score: 15
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #5:

score: 15
Accepted
time: 790ms
memory: 13848kb

input:

1000
96341
68443
37369
95002
5050
28444
863
40283
5948
58559
90074
93374
20434
66458
42427
81860
19058
44240
61491
29065
18196
59230
70644
48078
44160
52618
31944
3993
66326
63711
62648
80986
90080
12593
36140
908
97838
9909
62779
18661
92388
86436
83715
49365
10604
17467
65898
31682
64543
37267
202...

output:

24
1 -1 -1 2 2 2 2 -2 -2 9 9 9 9 9 9 -9 -18 63 63 63 63 -63 -63 -63 
23
-1 -1 1 1 1 2 -5 5 10 10 10 10 10 10 -10 -10 -10 -10 -10 -10 -20 87 -87 
22
1 -1 -1 -2 -2 -2 -2 2 2 4 4 13 13 13 13 13 13 -13 -13 -26 91 -91 
24
-1 -1 1 1 1 -3 -3 -3 3 3 3 12 12 12 12 12 12 12 -12 -12 -12 -12 24 24 
18
1 1 -1 -1...

result:

ok Accepted

Subtask #6:

score: 25
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #6:

score: 25
Accepted
time: 790ms
memory: 14040kb

input:

1000
68691
709038
403562
87832
620545
194650
877186
754984
970483
972817
576860
95921
320214
328151
977559
803543
893740
413219
868313
153241
553644
186975
758312
166278
963660
596237
523965
976575
92819
743171
220709
536964
847991
151853
256090
912309
286952
609500
293131
143200
850426
155262
98688...

output:

23
-1 1 1 1 3 3 3 3 3 3 3 3 -3 -6 -6 -6 50 50 -50 -50 -50 -50 -50 
26
-1 -1 1 1 1 1 4 4 4 4 4 4 -4 -4 -8 28 28 28 28 28 28 -28 -28 -28 -28 -28 
27
1 -1 3 -3 -3 -6 -6 -6 -6 6 6 6 6 12 -39 39 78 78 78 -78 -78 -78 -78 -78 156 156 156 
25
-1 -1 1 1 1 1 1 5 5 5 5 -5 -5 -5 -5 10 10 10 55 55 55 -55 -55 -55...

result:

ok Accepted
English 繁體中文 简体中文

服务器时间: 2024-12-03 04:18:15 | 开源项目