QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#495477#9133. Function with Many Maximumsucup-team4504#AC ✓18ms7512kbC++141.4kb2024-07-27 21:08:212024-07-27 21:08:21

Judging History

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

  • [2024-07-27 21:08:21]
  • 评测
  • 测评结果:AC
  • 用时:18ms
  • 内存:7512kb
  • [2024-07-27 21:08:21]
  • 提交

answer

//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
//#define int long long
using namespace __gnu_pbds;
using namespace std;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

long long a[500010];

signed main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	int n=500000;
	int b;cin>>b;
	int now=1;a[1]=300000000000ll;
	for(int i=2;i<=b;i++){
		int m=n-now+1;
		long long cur=1ll*(m+1)*a[now],rem=(m-2)-cur%(m-2);
		long long X=(a[now]-rem)/(m-2)+1;
		a[now+1]=rem+X*(m-2);
		a[now+2]=(cur+a[now+1])/(m-2);
		assert(1ll*(m+1)*a[now]>1ll*(m-1)*a[now+1]);
		assert(1ll*(m+1)*a[now]+1ll*a[now+1]==1ll*(m-2)*a[now+2]);
		now+=2;
	}
	for(int i=now+1;i<=n;i++){
		int m=n-i+1;
		a[i]=a[i-1]+1;
		assert(1ll*m*a[i-1]>1ll*(m-2)*a[i]);
	}
	cout<<n<<'\n';
	for(int i=1;i<=n;i++) cout<<a[i]<<' ';
	cout<<'\n';
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 16ms
memory: 7512kb

input:

4

output:

500000
300000000000 300000199980 300002400010 300002699814 300004800049 300005199445 300007200117 300007200118 300007200119 300007200120 300007200121 300007200122 300007200123 300007200124 300007200125 300007200126 300007200127 300007200128 300007200129 300007200130 300007200131 300007200132 3000072...

result:

ok n=500000, max_a=300007700110, max_num=4 >= 4

Test #2:

score: 0
Accepted
time: 18ms
memory: 7464kb

input:

100000

output:

500000
300000000000 300000199980 300002400010 300002699814 300004800049 300005199445 300007200117 300007698873 300009600214 300009698108 300012000339 300012197135 300014400493 300014695959 300016800676 300017194580 300019200888 300019692998 300021601129 300021691233 300024001398 300024189250 3000264...

result:

ok n=500000, max_a=833320390939, max_num=100000 >= 100000

Extra Test:

score: 0
Extra Test Passed