Submission #54163972

Source Code Expand

Copy
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <list>
#include <numeric>
#include <iterator>
#include <math.h>
#include <set>
#include <functional>
#include <fstream>
#include <chrono>
#include <random>
#include <assert.h>
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <list>
#include <numeric>
#include <iterator>
#include <math.h>
#include <set>
#include <functional>
#include <fstream>
#include <chrono>
#include <random>
#include <assert.h>

using std::cin;
using std::cout;
#define all(x) begin(x), end(x)
#define isz(x) int(size(x))
#define forx(x, n) for(int x = 0; x < n; ++x)
using std::vector;
using std::string;
using std::pair;
using ll = long long;
using ull = unsigned long long;
using real = long double;
using uint = unsigned int;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vvvpii = vector<vvpii>;
 
const auto ready = []()
{
    cin.tie(0);
    std::ios_base::sync_with_stdio(false);
    return true;
}();

ll binpow(ll a, ll p, ll mod)
{
    if (p == 0) return 1 % mod;
    ll half = binpow(a, p / 2, mod);
    half = half * half % mod;
    if (p & 1) half = half * a % mod;
    return half;
}

namespace algos {
    namespace SegmentTreeLazyTraits {
        /*******************************************************************************
         *  Use Traits<Value,Extra> for definition of:
         *      1)  neutral element for `Value`;
         *      2)  neutral element for `Extra`;
         *      3)  how should combine `Extra` with `Value`;
         *      4)  how should combine `Value` with `Value` (children to root);
         *      5)  how should combine `Extra` with `Extra`;
         *  See examples below: TraitsMinAdd<Value, Extra>
         ******************************************************************************/

         /*******************************************************************************
          *  Available traits, implemented in header file SegmentTreeLazyTraits.hpp
          ******************************************************************************/
        template<typename Value, typename Extra> struct LazyMinAdd;
        template<typename Value, typename Extra> struct LazyMaxAdd;
        template<typename Value, typename Extra> struct LazySumSet;
        template<typename Value, typename Extra> struct LazySumMul;
        template<typename Value, typename Extra> struct LazyGeomSumMul;

        /*******************************************************************************
         *  Traits for minimal value on segment.
         *  Get-query:    get minimal value in segment [l, r]
         *  Update-query: add const to each value in segment [l, r]
         ******************************************************************************/
        template<typename Value, typename Extra>
        struct LazyMinAdd {
            // Definition of neutral element for `Value`:
            static Value valueNeutral() { return std::numeric_limits<Value>::max(); }
            // Definition of neutral element for `Extra`:
            static Extra extraNeutral() { return Extra(0); }
            // Definition of how should combine `Extra` with `Value`:
            template<typename Node>
            static Value getValue(const Node& src) {
                return src.value() + src.extra();
            }
            // Definition of how should combine `Value` with `Value` (children to root):
            template<typename NodeRoot, typename NodeLt, typename NodeRt>
            static void pull(NodeRoot root, const NodeLt& lt, const NodeRt& rt) {
                root.value() = std::min(getValue(lt), getValue(rt));
            }
            // Definition of how should combine `Extra` with `Extra`:
            template<typename NodeDst, typename NodeSrc>
            static void push(NodeDst dst, const NodeSrc& src) {
                dst.extra() += src.extra();
            }
        };

        /*******************************************************************************
         *  Traits for maximal value on segment.
         *  Get-query:    get maximal value in segment [l, r]
         *  Update-query: add const to each value in segment [l, r]
         ******************************************************************************/
        template<typename Value, typename Extra>
        struct LazyMaxAdd {
            // Definition of neutral element for `Value`:
            static Value valueNeutral() { return std::numeric_limits<Value>::min(); }
            // Definition of neutral element for `Extra`:
            static Extra extraNeutral() { return Extra(0); }
            // Definition of how should combine `Extra` with `Value`:
            template<typename Node>
            static Value getValue(const Node& src) {
                return src.value() + src.extra();
            }
            // Definition of how should combine `Value` with `Value` (children to root):
            template<typename NodeRoot, typename NodeLt, typename NodeRt>
            static void pull(NodeRoot root, const NodeLt& lt, const NodeRt& rt) {
                root.value() = std::max(getValue(lt), getValue(rt));
            }
            // Definition of how should combine `Extra` with `Extra`:
            template<typename NodeDst, typename NodeSrc>
            static void push(NodeDst dst, const NodeSrc& src) {
                dst.extra() += src.extra();
            }
        };

        /*******************************************************************************
         *  Traits for sum of values on segment.
         *  Get-query:    sum of values on segment [l, r]
         *  Update-query: set const to each value in segment [l, r]
         ******************************************************************************/
        template<typename Value, typename Extra>
        struct LazySumSet {
            // Definition of neutral element for `Value`:
            static Value valueNeutral() { return Value(0); }
            // Definition of neutral element for `Extra`:
            static Extra extraNeutral() { return Extra(-1); }
            // Definition of how should combine `Extra` with `Value`:
            template<typename Node>
            static Value getValue(const Node& src) {
                return src.extra() == extraNeutral() ? src.value() : src.len() * src.extra();
            }
            // Definition of how should combine `Value` with `Value` (children to root):
            template<typename NodeRoot, typename NodeLt, typename NodeRt>
            static void pull(NodeRoot root, const NodeLt& lt, const NodeRt& rt) {
                root.value() = getValue(lt) + getValue(rt);
            }
            // Definition of how should combine `Extra` with `Extra`:
            template<typename NodeDst, typename NodeSrc>
            static void push(NodeDst dst, const NodeSrc& src) {
                dst.extra() = src.extra();
            }
        };

        /*******************************************************************************
         *  Traits for sum on segment with addition.
         *  Get-query:    sum of values on segment [l, r]
         *  Update-query: add const to each value on segment [l, r]
         ******************************************************************************/
        template<typename Value, typename Extra>
        struct LazySumAdd {
            // Definition of neutral element for `Value`:
            static Value valueNeutral() { return Value(0); }
            // Definition of neutral element for `Extra`:
            static Extra extraNeutral() { return Extra(0); }
            // Definition of how should combine `Extra` with `Value`:
            template<typename Node>
            static Value getValue(const Node& src) {
                return src.value() + src.extra() * src.len();
            }
            // Definition of how should combine `Value` with `Value` (children to root):
            template<typename NodeRoot, typename NodeLt, typename NodeRt>
            static void pull(NodeRoot root, const NodeLt& lt, const NodeRt& rt) {
                root.value() = getValue(lt) + getValue(rt);
            }
            // Definition of how should combine `Extra` with `Extra`:
            template<typename NodeDst, typename NodeSrc>
            static void push(NodeDst dst, const NodeSrc& src) {
                dst.extra() += src.extra();
            }
        };

        template<typename Value, typename Extra>
        struct LazySumMul {
            // Definition of neutral element for `Value`:
            static Value valueNeutral() { return Value(0); }
            // Definition of neutral element for `Extra`:
            static Extra extraNeutral() { return Extra(1); }
            // Definition of how should combine `Extra` with `Value`:
            template<typename Node>
            static Value getValue(const Node& src) {
                return src.value() * src.extra();
            }
            // Definition of how should combine `Value` with `Value` (children to root):
            template<typename NodeRoot, typename NodeLt, typename NodeRt>
            static void pull(NodeRoot root, const NodeLt& lt, const NodeRt& rt) {
                root.value() = getValue(lt) + getValue(rt);
            }
            // Definition of how should combine `Extra` with `Extra`:
            template<typename NodeDst, typename NodeSrc>
            static void push(NodeDst dst, const NodeSrc& src) {
                dst.extra() *= src.extra();
            }
        };

    } // namespace SegmentTreeLazyTraits
} // namespace algos

namespace SegmentTreeLazy {
    using namespace algos::SegmentTreeLazyTraits;
    /*******************************************************************************
     *  SegmentTree<Value, Extra, Traits> - segment tree class with lazy propagation, 0-indexed
     *  Default operations: minimal value on segment and addition on segment for int64_t type
     *  Use Traits<Value,Extra> for definition of:
     *      1)  neutral element for `Value`;
     *      2)  neutral element for `Extra`;
     *      3)  how should combine `Extra` with `Value`;
     *      4)  how should combine `Value` with `Value` (children to root);
     *      5)  how should combine `Extra` with `Extra`;
     *  See examples below: TraitsMinAdd<Value, Extra>
     ******************************************************************************/

     /*******************************************************************************
      *  Available traits, implemented below
      ******************************************************************************/
    template<typename Value, typename Extra> using TraitsMinAdd = LazyMinAdd<Value, Extra>;
    template<typename Value, typename Extra> using TraitsMaxAdd = LazyMaxAdd<Value, Extra>;
    template<typename Value, typename Extra> using TraitsSumSet = LazySumSet<Value, Extra>;
    template<typename Value, typename Extra> using TraitsSumMul = LazySumMul<Value, Extra>;

    /*******************************************************************************
     *  SegmentTree, see description above
     ******************************************************************************/
    template<typename Value = int64_t, typename Extra = int64_t, typename Traits = TraitsMinAdd<Value, Extra> >
    struct SegmentTree {

        /*******************************************************************************
         *  Node class
         ******************************************************************************/
        struct Node {
            Value value;

            Extra extra;

            Node(Value value_ = Traits::valueNeutral(), Extra extra_ = Traits::extraNeutral())
                : value(value_), extra(extra_) { }

            Value getValue(int l, int r) const { return Traits::getValue(NodeWrapper<Node>(l, r, *this)); }
        };

        /*******************************************************************************
         *  NodeWrapper class
         ******************************************************************************/
        template<typename NodeType>
        struct NodeWrapper {
            int l, r;
            NodeType node;
            NodeWrapper(int l_, int r_, NodeType node_)
                : l(l_), r(r_), node(node_) { }
            int  left() const { return l; }
            int right() const { return r; }
            int   mid() const { return (l + r) / 2; }
            int   len() const { return r - l + 1; }
            Value& value() { return node.value; }
            Extra& extra() { return node.extra; }
            const Value& value() const { return node.value; }
            const Extra& extra() const { return node.extra; }
        };

        /*******************************************************************************
         *  SegmentTree public data: n - number of items, data - vector for nodes
         ******************************************************************************/
        int n; std::vector<Node> data;


        /*******************************************************************************
         *  Resize segment tree data to needed size
         ******************************************************************************/
        void resize(int n_) {
            n = n_;
            data.assign(2 * n - 1, Node());
        }

        /*******************************************************************************
         *  Lazy propagation from node to its children
         ******************************************************************************/
        void push(int v, int l, int r, int m) {
            if (data[v].extra != Traits::extraNeutral()) {
                Traits::push(
                    NodeWrapper<Node&>(l, m, data[v + 1]),
                    NodeWrapper<const Node&>(l, r, data[v])
                );
                Traits::push(
                    NodeWrapper<Node&>(m + 1, r, data[v + 2 * (m - l + 1)]),
                    NodeWrapper<const Node&>(l, r, data[v])
                );
                data[v].extra = Traits::extraNeutral();
            }
        }

        /*******************************************************************************
         *  Update node using children values
         ******************************************************************************/
        void pull(int v, int l, int r, int m) {
            assert(data[v].extra == Traits::extraNeutral());
            Traits::pull(
                NodeWrapper<Node&>(l, r, data[v]),
                NodeWrapper<const Node&>(l, m, data[v + 1]),
                NodeWrapper<const Node&>(m + 1, r, data[v + 2 * (m - l + 1)])
            );
        }

        /*******************************************************************************
         *  Build segtree from array with given values
         ******************************************************************************/
        template<typename T>
        void build(const std::vector<T>& arr, const int v, const int tl, const int tr) {
            if (tl == tr) {
                data[v] = Node(arr[tl]);
            }
            else {
                const int tm = (tl + tr) / 2;
                build(arr, v + 1, tl, tm);
                build(arr, v + 2 * (tm - tl + 1), tm + 1, tr);
                pull(v, tl, tr, tm);
            }
        }

        template<typename T>
        void build(const std::vector<T>& arr) {
            resize((int)arr.size());
            build(arr, 0, 0, n - 1);
        }

        /*******************************************************************************
         *  Get-query on range [ql, qr]
         ******************************************************************************/
        Node get(int ql, int qr, const int v, const int tl, const int tr) {
            if (ql == tl && qr == tr) {
                return data[v];
            }
            else {
                int tm = (tl + tr) / 2;
                push(v, tl, tr, tm);
                Node ret;
                if (qr <= tm) {
                    ret = get(ql, qr, v + 1, tl, tm);
                }
                else if (ql > tm) {
                    ret = get(ql, qr, v + 2 * (tm - tl + 1), tm + 1, tr);
                }
                else {
                    const auto lt = get(ql, tm, v + 1, tl, tm);
                    const auto rt = get(tm + 1, qr, v + 2 * (tm - tl + 1), tm + 1, tr);
                    Traits::pull(
                        NodeWrapper<Node&>(ql, qr, ret),
                        NodeWrapper<const Node&>(ql, tm, lt),
                        NodeWrapper<const Node&>(tm + 1, qr, rt)
                    );
                }
                pull(v, tl, tr, tm);
                return ret;
            }
        }

        Value get(const int ql, const int qr) { return get(ql, qr, 0, 0, n - 1).getValue(ql, qr); }

        /*******************************************************************************
         *  Update query on range [ql, qr] by extra
         ******************************************************************************/
        void update(const int ql, const int qr, const Extra& extra, const int v, const int tl, const int tr) {
            if (ql == tl && tr == qr) {
                Traits::push(
                    NodeWrapper<Node&>(tl, tr, data[v]),
                    NodeWrapper<Node>(ql, qr, Node(Traits::valueNeutral(), extra))
                );
            }
            else {
                int tm = (tl + tr) / 2;
                push(v, tl, tr, tm);
                if (qr <= tm) {
                    update(ql, qr, extra, v + 1, tl, tm);
                }
                else if (ql > tm) {
                    update(ql, qr, extra, v + 2 * (tm - tl + 1), tm + 1, tr);
                }
                else {
                    update(ql, tm, extra, v + 1, tl, tm);
                    update(tm + 1, qr, extra, v + 2 * (tm - tl + 1), tm + 1, tr);
                }
                pull(v, tl, tr, tm);
            }
        }

        void update(const int ql, const int qr, const Extra& extra) {
            update(ql, qr, extra, 0, 0, n - 1);
        }

    };

} // namespace SegmentTreeLazy

void solve()
{
    int n, k;
    cin >> n >> k;

    vi vec(n);
    forx(i, n) cin >> vec[i];

    if (k > 0)
    {
        std::sort(all(vec));
        cout << "Yes\n";
        for (auto& el : vec) cout << el << " ";
        cout << "\n";
    }
    else
    {
        ll tmp = std::accumulate(all(vec), 0LL);
        if (tmp < k) cout << "No\n";
        else
        {
            cout << "Yes\n";
            std::sort(all(vec));
            std::reverse(all(vec));
            for (auto& el : vec) cout << el << " ";
            cout << "\n";
        }
    }
}

int main() 
{
    int t = 1;
    while (t--) solve();
    return 0;
}

Submission Info

Submission Time
Task A - Partition
User Anatoly_ig
Language C++ 20 (gcc 12.2)
Score 300
Code Size 19401 Byte
Status AC
Exec Time 31 ms
Memory 3868 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 48
Set Name Test Cases
Sample 00-sample-001.txt, 00-sample-002.txt, 00-sample-003.txt
All 00-sample-001.txt, 00-sample-002.txt, 00-sample-003.txt, 01-handmade-001.txt, 01-handmade-002.txt, 01-handmade-003.txt, 01-handmade-004.txt, 01-handmade-005.txt, 01-handmade-006.txt, 01-handmade-007.txt, 01-handmade-008.txt, 01-handmade-009.txt, 01-handmade-010.txt, 01-handmade-011.txt, 01-handmade-012.txt, 01-handmade-013.txt, 01-handmade-014.txt, 01-handmade-015.txt, 01-handmade-016.txt, 01-handmade-017.txt, 01-handmade-018.txt, 01-handmade-019.txt, 01-handmade-020.txt, 01-handmade-021.txt, 01-handmade-022.txt, 01-handmade-023.txt, 01-handmade-024.txt, 01-handmade-025.txt, 02-random-001.txt, 02-random-002.txt, 02-random-003.txt, 02-random-004.txt, 02-random-005.txt, 02-random-006.txt, 02-random-007.txt, 02-random-008.txt, 02-random-009.txt, 02-random-010.txt, 02-random-011.txt, 02-random-012.txt, 02-random-013.txt, 02-random-014.txt, 02-random-015.txt, 02-random-016.txt, 02-random-017.txt, 02-random-018.txt, 02-random-019.txt, 02-random-020.txt
Case Name Status Exec Time Memory
00-sample-001.txt AC 1 ms 3520 KB
00-sample-002.txt AC 1 ms 3456 KB
00-sample-003.txt AC 1 ms 3472 KB
01-handmade-001.txt AC 1 ms 3460 KB
01-handmade-002.txt AC 1 ms 3508 KB
01-handmade-003.txt AC 1 ms 3452 KB
01-handmade-004.txt AC 1 ms 3408 KB
01-handmade-005.txt AC 1 ms 3512 KB
01-handmade-006.txt AC 1 ms 3316 KB
01-handmade-007.txt AC 1 ms 3432 KB
01-handmade-008.txt AC 1 ms 3412 KB
01-handmade-009.txt AC 1 ms 3456 KB
01-handmade-010.txt AC 1 ms 3520 KB
01-handmade-011.txt AC 1 ms 3460 KB
01-handmade-012.txt AC 1 ms 3472 KB
01-handmade-013.txt AC 1 ms 3408 KB
01-handmade-014.txt AC 1 ms 3316 KB
01-handmade-015.txt AC 23 ms 3804 KB
01-handmade-016.txt AC 12 ms 3868 KB
01-handmade-017.txt AC 12 ms 3820 KB
01-handmade-018.txt AC 12 ms 3424 KB
01-handmade-019.txt AC 24 ms 3548 KB
01-handmade-020.txt AC 17 ms 3572 KB
01-handmade-021.txt AC 12 ms 3472 KB
01-handmade-022.txt AC 9 ms 3460 KB
01-handmade-023.txt AC 8 ms 3592 KB
01-handmade-024.txt AC 31 ms 3836 KB
01-handmade-025.txt AC 29 ms 3784 KB
02-random-001.txt AC 1 ms 3384 KB
02-random-002.txt AC 1 ms 3420 KB
02-random-003.txt AC 1 ms 3380 KB
02-random-004.txt AC 1 ms 3500 KB
02-random-005.txt AC 1 ms 3476 KB
02-random-006.txt AC 1 ms 3424 KB
02-random-007.txt AC 1 ms 3476 KB
02-random-008.txt AC 1 ms 3524 KB
02-random-009.txt AC 1 ms 3472 KB
02-random-010.txt AC 1 ms 3516 KB
02-random-011.txt AC 17 ms 3524 KB
02-random-012.txt AC 5 ms 3376 KB
02-random-013.txt AC 31 ms 3828 KB
02-random-014.txt AC 18 ms 3504 KB
02-random-015.txt AC 4 ms 3424 KB
02-random-016.txt AC 2 ms 3516 KB
02-random-017.txt AC 3 ms 3524 KB
02-random-018.txt AC 6 ms 3464 KB
02-random-019.txt AC 10 ms 3560 KB
02-random-020.txt AC 29 ms 3836 KB

2025-03-09 (Sun)
18:27:36 +00:00