做神秘顾客哪个网站好,谷歌网站推广软件,邯郸企业做网站费用,1000元能否做网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
不难想到#xff0c;长度为nnn的数组最多的满足条件的三元组序列是1,2,3....,n1,2,3....,n1,2,3....,n#xff0c;对于每一个位置贡献为i−12\frac{i-1}{2}2i−1#xff0c;那么如果m…传送门
文章目录题意思路题意 思路
不难想到长度为nnn的数组最多的满足条件的三元组序列是1,2,3....,n1,2,3....,n1,2,3....,n对于每一个位置贡献为i−12\frac{i-1}{2}2i−1那么如果m∑i1ni−12m\sum _{i1}^{n} \frac{i-1}{2}m∑i1n2i−1的时候无解。 考虑如果∑i1ni−12≥m\sum _{i1}^{n} \frac{i-1}{2}\ge m∑i1n2i−1≥m的情况我们怎么构造。 当∑i1ni−12m\sum _{i1}^{n} \frac{i-1}{2} m∑i1n2i−1m的时候显然构造1,2,...,n1,2,...,n1,2,...,n即可。否则我们还是构造1,2,...,x1,2,...,x1,2,...,x当到xxx的时候总贡献summsummsumm了我们假设多出来yyy个即sum−mysum-mysum−my也就是说我们要在前面减去yyy对贡献怎么去掉呢我们考虑将它向右平移y∗2y*2y∗2个单位具体的可以看下图 对于多出来的点我们从1e9−k∗(maxans1)1e9-k*(max_{ans}1)1e9−k∗(maxans1)可以证明这样构造是正确的。 这样我们直接构造就好啦构造不出来直接输出−1-1−1即可。
// Problem: E. Kuroni and the Score Distribution
// Contest: Codeforces - Ozon Tech Challenge 2020 (Div.1 Div.2, Rated, T-shirts prizes!)
// URL: https://codeforces.com/contest/1305/problem/E
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int ans[N];bool check() {int now0;for(int i1;in;i) {ans[i]i; now(i-1)/2;if(nowm) {ans[i]2*(now-m);for(int jn,k0;ji;j--,k) ans[j]1e9-(ans[i]1)*k;for(int i1;in;i) printf(%d ,ans[i]);puts();return true;}}return false;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cinnm;if(!check()) puts(-1);return 0;
}
/**/
