QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#494946#9133. Function with Many Maximumsucup-team052#AC ✓21ms14296kbC++231.2kb2024-07-27 17:46:592024-07-27 17:47:00

Judging History

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

  • [2024-07-27 17:47:00]
  • 评测
  • 测评结果:AC
  • 用时:21ms
  • 内存:14296kb
  • [2024-07-27 17:46:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
inline int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
inline int mul(int x,int y) {return 1ULL*x*y%mod;}
#define int long long
#define N 500005
int a[N],sum[N],val[N],n;
const int M=1000000000000;
void push(int v)
{
	a[++n]=v;
	sum[n]=sum[n-1]+v;
	val[n]=sum[n]+v*n;
	// printf("%lld : %lld\n",n,a[n]);
	// printf("%lld : %lld\n",n,val[n]);
}
signed main()
{
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	for(int i=1;i<=50000;i++)
	{
		push(M-i+1);
	}
	int V=val[n];
	for(int i=1;i<=100000;i++)
	{
		int ok=0,tv=V-sum[n];
		for(int j=1;j<=10;j++)
		{
			int rs=tv%(n+j+1);
			int cv=tv/(n+j+1);
			int diff=cv*(j-1)+j*(j-1)/2-rs;
			int gov=(n+j+1+diff)/(n+j+2);
			rs+=(n+j+1)*gov;
			cv-=gov;
			if(rs>a[n]*(j-1)-j*(j-1)) continue;
			// j-1 numbers, sum = rs
			// add cv
			// printf("%d\n",j);
			assert(j<=2);
			if(j>=2) push(rs);
			push(cv);
			ok=1;
			break;
			/*
			while(cv*(j-1)+j*(j-1)/2<rs)
			{
				rs+=n+j+1,cv--;
			}
			*/
		}
		assert(ok);
		// if(!ok) cout<<"bad "<<i<<endl;
	}
	cout<<n<<endl;
	for(int i=1;i<=n;i++) printf("%lld%c",a[i]," \n"[i==n]);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 21ms
memory: 14040kb

input:

4

output:

249997
1000000000000 999999999999 999999999998 999999999997 999999999996 999999999995 999999999994 999999999993 999999999992 999999999991 999999999990 999999999989 999999999988 999999999987 999999999986 999999999985 999999999984 999999999983 999999999982 999999999981 999999999980 999999999979 999999...

result:

ok n=249997, max_a=1000000000000, max_num=100001 >= 4

Test #2:

score: 0
Accepted
time: 16ms
memory: 14296kb

input:

100000

output:

249997
1000000000000 999999999999 999999999998 999999999997 999999999996 999999999995 999999999994 999999999993 999999999992 999999999991 999999999990 999999999989 999999999988 999999999987 999999999986 999999999985 999999999984 999999999983 999999999982 999999999981 999999999980 999999999979 999999...

result:

ok n=249997, max_a=1000000000000, max_num=100001 >= 100000

Extra Test:

score: 0
Extra Test Passed