CodeForces 1244G Running in Pairs

题意

找到长度为$n$的全排列$p$和$q$，使得$\sum\limits_{n=1}^n \max(p_i,q_i)$最大且不超过给定的$k$

分析

最小为$\sum\limits_{n=1}^n i$，最大为$\sum\limits_{n=1}^n \max(i,n-i+1)$，则从$\sum\limits_{n=1}^n i$开始操作，设置数组$a[]$，有$a[i]=i$，设当前可以取的区间为$[l,r]$，设置$sum=\sum\limits_{n=1}^n i$，如果$r >= a[i] \&\& sum + r - a[i] <= k$，则表示$a[i]$可以取$r$，否则只能取$l$

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
int a[maxn], b[maxn];

void solve() {
    int n, k;
    cin >> n >> k;
    if (k < (1 + n) * n / 2) {
        cout << -1;
        return;
    }
    int sum = 0;
    rep(i, 1, n)a[i] = i, b[i] = n - i + 1, sum += max(a[i], b[i]);
    if (sum < k) {
        cout << sum << '\n';
        rep(i, 1, n)cout << a[i] << ' ';
        cout << '\n';
        rep(i, 1, n)cout << b[i] << ' ';
        return;
    }
    int l = 1, r = n;
    sum = (1 + n) * n / 2;
    rep(i, 1, n) {
        if (r >= a[i] && sum + r - a[i] <= k) {
            sum += r - a[i];
            b[i] = r--;
        } else
            b[i] = l++;
    }
    cout << k << '\n';
    rep(i, 1, n)cout << a[i] << ' ';
    cout << '\n';
    rep(i, 1, n)cout << b[i] << ' ';
}

signed main() {
    while (T--)
        solve();
    return 0;
}