結果

問題 No.1635 Let’s Sort Integers!!
ユーザー Edeeva
提出日時 2025-03-31 17:48:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,126 bytes
コンパイル時間 3,364 ms
コンパイル使用メモリ 226,912 KB
実行使用メモリ 50,560 KB
最終ジャッジ日時 2025-03-31 17:50:06
合計ジャッジ時間 28,825 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 76 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define rep(i,a,b) for (int i = a; i < b; i++)
#define mp make_pair
#define pii pair<int,int> 
#define pb push_back
#define pll pair<long long, long long>
#define fi first
#define se second
#define blahaj ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int,int>, null_type,  less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef long long ll;
typedef long double ld;
ll mod = 1000000007;
const int N = 200000;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const char dir[4]{'D','R','U','L'};
#define all(x) begin(x), end(x)
string yes = "YES\n";
string no = "NO\n";
ll inf = 1e9;

int main()
{
    blahaj;
    ll n, k;
    cin >> n >> k;
    if (k < n - 1) cout << "-1\n";
    else if (n == 2)
    {
        if (k == 1) cout << 1 << ' ' << 2 << "\n";
        else cout << "-1\n";
    }
    else if (k <= (n - 1) + (n - 2))
    {
        ll need = k - (n - 1);
        ll val = n - need;
        cout << 1 << ' ';
        for (int i = 2; i < n; i++) if (i != val) cout << i << ' ';
        cout << n <<  ' ';
        if (need) cout << val << ' ';
        cout << "\n";
    }
    else
    {
        vector<bool> used(n + 2, false);
        vector<int> ans;
        ll last = n / 2;
        ans.pb(last);
        ll lo = 1;
        ll hi = n;
        ll need = k;
        set<int> rest;
        for (int i = 0; i <= n + 1; i++) rest.insert(i);
        rest.erase(last);
        for (int i = 1; i < n && need; i++)
        {
            int pick;
           // cout << "NEED " << need << ' ' << lo << ' ' << hi << ' ' << last << endl;
            if (i % 2) // go high
            {
                while (!rest.count(hi)) hi--;
                if (hi < last) continue;
                ll mxdiff = hi - last;
                if (mxdiff >= need) 
                {
                    pick = last + need;
                }
                else 
                {
                    pick = hi;
                }
               // cout << "PICKK " << last << endl;;
                auto it = rest.upper_bound(pick);
                it--;
                if (*it < last) continue;
                need -= abs(last - *it);
                last = *it;
                ans.pb(last);
                rest.erase(last);
            }
            else 
            {
                while (!rest.count(lo)) lo++;
                if (lo > last) continue;
               // cout << "LOW " << lo << endl;
                ll mxdiff = last - lo;
                if (mxdiff >= need)
                {
                    //cout << "LAST " << last << ' ' << need << endl;
                    pick = last - need;
                }
                else
                {
                    pick = lo;
                }
                //cout << "PICK " << last << endl;
                auto it = rest.lower_bound(pick);
                if (*it > last) continue;
                need -= abs(last - *it);
                last = *it;
                rest.erase(last);
                ans.pb(last);
            }
        }
        if (need )
        {
            cout << "-1\n";
            return 0;
        }
        int m = ans.size();
        for (int j = 0; j + 1 < m; j++)
        {
            int l = min(ans[j], ans[j + 1]);
            int r = max(ans[j], ans[j + 1]);
            cout << ans[j] << ' ';
            vector<int> between;
            auto it = rest.lower_bound(l);
            while (*it <= r)
            {
                int x = *it;
                between.pb(x);
                rest.erase(x);
                it = rest.lower_bound(l);
            }
            if (ans[j] > ans[j + 1]) reverse(all(between));
            for (auto x : between) cout << x << ' ';
        }
        cout << ans[m - 1] << "\n";
    }
}
0