結果

問題 No.2567 A_1 > A_2 > ... > A_N
ユーザー highlighter
提出日時 2023-12-02 15:10:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 828 bytes
コンパイル時間 3,080 ms
コンパイル使用メモリ 246,612 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-26 18:14:02
合計ジャッジ時間 5,461 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long

bool solve(int N,int X,int a){
	//A[0]==aのとき可能か
	//a+(a-1)+...+(a-N+1)
	//(2*a-N+1)*N/2
	int sum=(2*a-N+1)*N/2;
	if(sum>=X){
		return true;
	}
	return false;
}

int solve2(int N,int X,int r){
	int l=N-1;
	while((r-l)>1){
		int m=(l+r)/2;
		if(solve(N,X,m)){
			r=m;
			continue;
		}
		l=m;
	}
	return r;
}

signed main() {
	int T;
	cin >> T;
	for(;T--;){
		int N,X;
		cin >> N >> X;
		int sum=N*(N+1)/2;
		if(sum>X){
			cout << -1 << endl;
			continue;
		}
		int k=1000000000000000000LL;
		sum=0;
		int x=X;
		vector<int> A(N);
		for(int i=N;i>=2;i--){
			int t=solve2(i,X,k);
			sum+=t;
			A[N-i]=t;
			k=t-1;
			X-=t;
		}
		A[N-1]=x-sum;
		if((x-sum)<=0){
			cout << -1 << endl;
		}
		for(int i : A){
			cout << i << " ";
		}
		cout << endl;
	}
}
0