KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200） E - Patisserie ABC 2
题意
将(n^3)个三元组((i,j,k),1le i,j,kle n)进行排序，问第(k)个三元组是什么
排序先按总和(i+j+k)进行排序，小的在前
相同和的情况下按(i ightarrow j ightarrow k)的顺序比对大小，小的在前（字典序小的在前）
思路
打表找规律，先按和进行分组，可得对于前几个(n)，和为(jin[3,3*n])的三元组数量如下
由于呈左右对称规律，折半后表为（标红表示不进行对称处理）
发现从第一个数到标绿的数字位置，之前每个数均为(1+2+cdots+p)（(p)表示位置），每次增幅即下标，直到下标为(n)时截止
而从标绿数字的下一个数开始，每次增幅从(n-2)开始依次递减(2)
以(n=7)为例，第二个数到第七个数较前一个数的增幅为(+2,+3,+4,+5,+6,+7)，从第八个数开始变为(+5,+3,+1)
故根据上述规律，对于每组数据输入的(n)，我们可以将和为(sum)时的三元组数量(tmp[sum])预处理出
int i=3; //sum的范围为3*1~3*n
for(int j=1;j<=n;i++,j++)
tmp[i]=tmp[i-1]+j; //前n个数，每次增幅为j=1~n
for(int j=n-2;j>0;i++,j-=2)
tmp[i]=tmp[i-1]+j; //第n+1个数开始，每次增幅从n开始每次-2
if(n%2) //这里处理对称，分奇偶处理
{
int m=i-1;
for(;i<=3*n;i++)
tmp[i]=tmp[m-(i-m)];
}
else
{
int m=i;
for(;i<=3*n;i++)
tmp[i]=tmp[m-1-(i-m)];
}
根据上方的预处理，我们可以得出(n,k)的限制下三元组((i,j,k))的和(sum)为多少
ll sum=3;
while(k>tmp[sum])
{
k-=tmp[sum];
sum++;
}
由于相同和的情况下是按照字典序进行排序的， 所以可以按从小到大的顺序枚举第一个数(a)，并得出后两个数相加之和(x=sum-a)
对于二元组((j,k),1le j,kle n,j+k=sum)的情况数
明显当(sumle n)时，种类数只有(sum-1)种：((1,sum-1),(2,sum-2),cdots,(sum-1,1))
故对于(sumin[2,n+1])，种类数为(1,2,cdots,n)
当(sumgt n)时，种类数呈对称状逐级递减
即对于(sumin[n+2,2n])，种类数为(n-1,n-2,cdots,1)
由于(n)固定，这部分也可预处理成(tmp2)数组
rep(i,2,n+1)
tmp2[i]=i-1;
rep(i,n+2,n+n)
tmp2[i]=n*2+1-i;
于是枚举第一个数(a)，若(kgt tmp2[sum-a])，则第一个数比(a)大，继续枚举下去且让(k-=tmp2[sum-a])
直到(kle tmp2[sum-a])，此时(a)便固定了下来，由于(nle 10^6)，于是便可以直接枚举第二个数，求出第(k)个合法方案输出即可
程序
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
ll tmp[3000050],tmp2[2000050];
void init(int n)
{
int i=3;
for(int j=1;j<=n;i++,j++)
tmp[i]=tmp[i-1]+j;
for(int j=n-2;j>0;i++,j-=2)
tmp[i]=tmp[i-1]+j;
if(n%2)
{
int m=i-1;
for(;i<=3*n;i++)
tmp[i]=tmp[m-(i-m)];
}
else
{
int m=i;
for(;i<=3*n;i++)
tmp[i]=tmp[m-1-(i-m)];
}
rep(i,2,n+1)
tmp2[i]=i-1;
rep(i,n+2,n*2)
tmp2[i]=n*2+1-i;
}
void solve()
{
int n;
ll k;
cin>>n>>k;
init(n);
ll sum=3;
while(k>tmp[sum])
{
k-=tmp[sum];
sum++;
}
rep(a,sum-2*n,sum-2)
{
if(a<1)
continue;
int x=sum-a;
if(k>tmp2[x])
k-=tmp2[x];
else
{
cout<<a<<' ';
int b,c;
if(x>=n+1)
b=x-n,c=n;
else
b=1,c=x-1;
while(--k)
b++,c--;
cout<<b<<' '<<c<<'
';
assert(b>=1&&b<=n&&c>=1&&c<=n);
return;
}
}
}
int main()
{
closeSync;
//multiCase
{
solve();
}
return 0;
}