#483712 (C++17) No.1055 牛歩

提出ソース

結果

問題	No.1055 牛歩
ユーザー	jell
提出日時	2020-05-19 18:29:52
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	110 ms / 1,000 ms
コード長	15,805 bytes
コンパイル時間	3,204 ms
コンパイル使用メモリ	234,688 KB
実行使用メモリ	9,472 KB
最終ジャッジ日時	2024-10-01 22:56:46
合計ジャッジ時間	6,530 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	110 ms 9,472 KB
testcase_01	AC	42 ms 9,088 KB
testcase_02	AC	20 ms 6,816 KB
testcase_03	AC	20 ms 6,816 KB
testcase_04	AC	20 ms 6,816 KB
testcase_05	AC	20 ms 6,824 KB
testcase_06	AC	22 ms 6,816 KB
testcase_07	AC	20 ms 6,820 KB
testcase_08	AC	22 ms 6,816 KB
testcase_09	AC	18 ms 6,816 KB
testcase_10	AC	18 ms 6,816 KB
testcase_11	AC	18 ms 6,824 KB
testcase_12	AC	19 ms 6,820 KB
testcase_13	AC	19 ms 6,824 KB
testcase_14	AC	18 ms 6,820 KB
testcase_15	AC	19 ms 6,820 KB
testcase_16	AC	15 ms 6,816 KB
testcase_17	AC	16 ms 6,820 KB
testcase_18	AC	16 ms 6,820 KB
testcase_19	AC	16 ms 6,820 KB
testcase_20	AC	19 ms 6,820 KB
testcase_21	AC	20 ms 6,820 KB
testcase_22	AC	22 ms 6,816 KB
testcase_23	AC	22 ms 6,824 KB
testcase_24	AC	23 ms 6,816 KB
testcase_25	AC	23 ms 8,724 KB
testcase_26	AC	22 ms 8,664 KB
testcase_27	AC	25 ms 8,596 KB
testcase_28	AC	22 ms 8,732 KB
testcase_29	AC	28 ms 8,476 KB
testcase_30	AC	26 ms 8,724 KB
testcase_31	AC	7 ms 6,816 KB
testcase_32	AC	6 ms 6,820 KB
testcase_33	AC	7 ms 6,816 KB
testcase_34	AC	6 ms 6,820 KB
testcase_35	AC	8 ms 6,816 KB
testcase_36	AC	8 ms 6,820 KB
testcase_37	AC	6 ms 6,816 KB
testcase_38	AC	7 ms 6,824 KB
testcase_39	AC	2 ms 6,816 KB
testcase_40	AC	2 ms 6,820 KB
testcase_41	AC	2 ms 6,820 KB
testcase_42	AC	3 ms 6,820 KB
testcase_43	AC	2 ms 6,820 KB
testcase_44	AC	3 ms 6,820 KB
testcase_45	AC	3 ms 6,824 KB
testcase_46	AC	3 ms 6,816 KB
testcase_47	AC	3 ms 6,820 KB
testcase_48	AC	2 ms 6,820 KB
testcase_49	AC	2 ms 6,820 KB
testcase_50	AC	2 ms 6,820 KB
testcase_51	AC	2 ms 6,824 KB
testcase_52	AC	2 ms 6,820 KB
testcase_53	AC	2 ms 6,816 KB
testcase_54	AC	2 ms 6,820 KB
testcase_55	AC	2 ms 6,816 KB
testcase_56	AC	2 ms 6,816 KB
testcase_57	AC	2 ms 6,820 KB
testcase_58	AC	2 ms 6,820 KB
testcase_59	AC	2 ms 6,820 KB
testcase_60	AC	2 ms 6,820 KB
testcase_61	AC	2 ms 6,820 KB
testcase_62	AC	2 ms 6,816 KB
testcase_63	AC	2 ms 6,816 KB
testcase_64	AC	2 ms 6,820 KB
testcase_65	AC	2 ms 6,816 KB
testcase_66	AC	2 ms 6,820 KB
testcase_67	AC	2 ms 6,816 KB
testcase_68	AC	2 ms 6,820 KB
testcase_69	AC	2 ms 6,824 KB
testcase_70	AC	2 ms 6,816 KB
testcase_71	AC	2 ms 6,820 KB
testcase_72	AC	2 ms 6,820 KB
testcase_73	AC	2 ms 6,820 KB
testcase_74	AC	2 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

/* preprocessor start */
#ifdef LOCAL
//*
    #define _GLIBCXX_DEBUG  // gcc
/*/
    #define _LIBCPP_DEBUG 0 // clang
//*/
    #define __clock__
    // #define __buffer_check__
#else
    #pragma GCC optimize("Ofast")
/*
    #define _GLIBCXX_DEBUG  // gcc
/*/
//    #define _LIBCPP_DEBUG 0 // clang
//*/
    // #define __buffer_check__
    // #define NDEBUG
#endif
#define __precision__ 15
#define iostream_untie true
#include <bits/stdc++.h>
#include <ext/rope>
#define __all(v) std::begin(v), std::end(v)
#define __rall(v) std::rbegin(v), std::rend(v)
#define __popcount(n) __builtin_popcountll(n)
#define __clz32(n) __builtin_clz(n)
#define __clz64(n) __builtin_clzll(n)
#define __ctz32(n) __builtin_ctz(n)
#define __ctz64(n) __builtin_ctzll(n)
/* preprocessor end */

namespace std
{
    // hash
    template <class T> size_t hash_combine(size_t seed, T const &key) { return seed ^ (hash<T>()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2)); }
    template <class T, class U> struct hash<pair<T, U>> { size_t operator()(pair<T, U> const &pr) const { return hash_combine(hash_combine(0, pr.first), pr.second); } };
    template <class tuple_t, size_t index = tuple_size<tuple_t>::value - 1> struct tuple_hash_calc { static size_t apply(size_t seed, tuple_t const &t) { return hash_combine(tuple_hash_calc<tuple_t, index - 1>::apply(seed, t), get<index>(t)); } };
    template <class tuple_t> struct tuple_hash_calc<tuple_t, 0> { static size_t apply(size_t seed, tuple_t const &t) { return hash_combine(seed, get<0>(t)); } };
    template <class... T> struct hash<tuple<T...>> { size_t operator()(tuple<T...> const &t) const { return tuple_hash_calc<tuple<T...>>::apply(0, t); } };
    // iostream
    template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) { return is >> p.first >> p.second; }
    template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << p.first << ' ' << p.second; }
    template <class tuple_t, size_t index> struct tupleis { static istream &apply(istream &is, tuple_t &t) { tupleis<tuple_t, index - 1>::apply(is, t); return is >> get<index>(t); } };
    template <class tuple_t> struct tupleis<tuple_t, SIZE_MAX> { static istream &apply(istream &is, tuple_t &t) { return is; } };
    template <class... T> istream &operator>>(istream &is, tuple<T...> &t) { return tupleis<tuple<T...>, tuple_size<tuple<T...>>::value - 1>::apply(is, t); }
    template <> istream &operator>>(istream &is, tuple<> &t) { return is; }
    template <class tuple_t, size_t index> struct tupleos { static ostream &apply(ostream &os, const tuple_t &t) { tupleos<tuple_t, index - 1>::apply(os, t); return os << ' ' << get<index>(t); } };
    template <class tuple_t> struct tupleos<tuple_t, 0> { static ostream &apply(ostream &os, const tuple_t &t) { return os << get<0>(t); } };
    template <class... T> ostream &operator<<(ostream &os, const tuple<T...> &t) { return tupleos<tuple<T...>, tuple_size<tuple<T...>>::value - 1>::apply(os, t); }
    template <> ostream &operator<<(ostream &os, const tuple<> &t) { return os; }
    template <class Container, typename Value = typename Container::value_type, enable_if_t<!is_same<decay_t<Container>, string>::value, nullptr_t> = nullptr>
    istream& operator>>(istream& is, Container &cont) { for(auto&& e : cont) is >> e; return is; }
    template <class Container, typename Value = typename Container::value_type, enable_if_t<!is_same<decay_t<Container>, string>::value, nullptr_t> = nullptr>
    ostream& operator<<(ostream& os, const Container &cont) { bool flag = 1; for(auto&& e : cont) flag ? flag = 0 : (os << ' ', 0), os << e; return os; }
} // namespace std

namespace setting
{
    using namespace std;
    using namespace chrono;
    system_clock::time_point start_time, end_time;
    long long get_elapsed_time() { end_time = system_clock::now(); return duration_cast<milliseconds>(end_time - start_time).count(); }
    void print_elapsed_time() { cerr << "\n----- Exec time : " << get_elapsed_time() << " ms -----\n\n"; }
    void buffer_check() { char bufc; if(cin >> bufc) cerr << "\n\033[1;35mwarning\033[0m: buffer not empty.\n"; }
    struct setupper
    {
        setupper()
        {
            if(iostream_untie) ios::sync_with_stdio(false), cin.tie(nullptr);
            cout << fixed << setprecision(__precision__);
    #ifdef stderr_path
            freopen(stderr_path, "a", stderr);
    #endif
    #ifdef LOCAL
            cerr << fixed << setprecision(__precision__) << boolalpha << "\n----- stderr at LOCAL -----\n\n";
    #endif
    #ifdef __clock__
            start_time = system_clock::now();
            atexit(print_elapsed_time);
    #endif
    #ifdef __buffer_check__
            atexit(buffer_check);
    #endif
        }
    } __setupper; // struct setupper
} // namespace setting

#ifdef __clock__
    #include "clock.hpp"
#else
    #define build_clock() ((void)0)
    #define set_clock() ((void)0)
    #define get_clock() ((void)0)
#endif

#ifdef LOCAL
    #include "dump.hpp"
#else
    #define dump(...) ((void)0)
#endif

/* function utility start */
// lambda wrapper for recursive method.
template <class lambda_type>
class make_recursive
{
    lambda_type func;
public:
    make_recursive(lambda_type &&f) : func(std::move(f)) {}
    template <class... Args> auto operator()(Args &&... args) const { return func(*this, std::forward<Args>(args)...); }
};
/*
template <class T, class... types> T read(types... args) noexcept { typename std::remove_const<T>::type obj(args...); std::cin >> obj; return obj; }
#define input(type, var, ...) type var{read<type>(__VA_ARGS__)}
*/
// substitute y for x if x > y.
template <class T> inline bool chmin(T &x, const T &y) { return x > y ? x = y, true : false; }
// substitute y for x if x < y.
template <class T> inline bool chmax(T &x, const T &y) { return x < y ? x = y, true : false; }
// binary search on discrete range.
template <class iter_type, class pred_type>
iter_type binary(iter_type __ok, iter_type __ng, pred_type pred)
{
    std::ptrdiff_t dist(__ng - __ok);
    while(std::abs(dist) > 1)
    {
        iter_type mid(__ok + dist / 2);
        if(pred(mid)) __ok = mid, dist -= dist / 2;
        else __ng = mid, dist /= 2;
    }
    return __ok;
}
// binary search on real numbers.
template <class pred_type>
long double binary(long double __ok, long double __ng, const long double eps, pred_type pred)
{
    while(std::abs(__ok - __ng) > eps)
    {
        long double mid{(__ok + __ng) / 2};
        (pred(mid) ? __ok : __ng) = mid;
    }
    return __ok;
}
// size of array.
template <class A, size_t N> size_t size(A (&array)[N]) { return N; }
// be careful that val is type-sensitive.
template <class T, class A, size_t N> void init(A (&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); }
/* functon utility end */

/* using alias start */
using namespace std;
using i32 = int_least32_t; using i64 = int_least64_t; using u32 = uint_least32_t; using u64 = uint_least64_t;
using p32 = pair<i32, i32>; using p64 = pair<i64, i64>;
template <class T, class Comp = less<T>> using heap = priority_queue<T, vector<T>, Comp>;
template <class T> using hashset = unordered_set<T>;
template <class Key, class Value> using hashmap = unordered_map<Key, Value>;
using namespace __gnu_cxx;
/* using alias end */

/* library start */



/* library end */

/* The main code follows. */

struct solver; template <class T = solver> void _main();
int main() { _main<>(); }

template <class solver>
void _main()
{
    unsigned t = 1;
#ifdef LOCAL
    t = 5;
#endif
    // t = -1; // infinite loop
    // cin >> t; // case number given

    while(t--) solver();
}

struct solver
{

    solver()
    {
        int n,m; cin>>n>>m;
        vector<int> pos(m);
        for(int &x: pos)
        {
            cin>>x; --x;
        }
        int Q; cin>>Q;
        struct ope { int time; int dir; };
        vector<vector<ope>> cmd(m);
        for(int i=0; i<Q; ++i)
        {
            int b; cin>>b; --b;
            cmd[b].emplace_back(ope{i,1});
        }

        for(int now=0; now<m; ++now)
        {
            int prel=now?pos[now-1]:-1;
            int w=pos[now]-prel;
            vector<p32> nop;
            // two-pointers
            {
                auto nvec=now?cmd[now-1]:vector<ope>();
                auto itr=begin(nvec);
                for(auto x:cmd[now])
                {
                    while(itr!=end(nvec) and itr->time<x.time)
                    {
                        nop.emplace_back(0,itr->dir);
                        ++itr;
                    }
                    nop.emplace_back(1,x.dir);
                }
                while(itr!=end(nvec))
                {
                    nop.emplace_back(0,itr->dir);
                    ++itr;
                }
            }

            vector<int> acc(nop.size());
            for(int i=0,prv=0; i<(int)nop.size(); ++i)
            {
                if(nop[i].first)
                {
                    acc[i]=prv-1;
                }
                else
                {
                    acc[i]=prv+nop[i].second;
                }
                prv=acc[i];
            }
            vector<int> sufx(nop.size());
            for(int i=nop.size(),prv=-1e6; i--; )
            {
                prv=sufx[i]=max(acc[i],prv);
            }

            if(!sufx.empty() and sufx[0]>=w)
            {
                cout << "NO" << "\n";
                // cerr << "at left!\n";
                return;
            }

            for(int i=0,cor=0,j=0; i<(int)nop.size(); ++i)
            {
                if(nop[i].first)
                {
                    int& ndir=cmd[now][j].dir;
                    if(sufx[i]+2+cor<w)
                    {
                        cor+=2;
                        ndir=-1;
                    }
                    dump(now,j,ndir);
                    ++j;
                }
            }
        }

        // check end
        {
            int npos=pos.back();
            for(auto [t,d]: cmd.back())
            {
                npos+=d;
                if(npos==n)
                {
                    cout << "NO" << "\n";
                    // cerr << "at center!\n";
                    return;
                }
            }
        }

/*
        int li,ri;
        for(li=0,ri=m-1; li<=ri; li++,ri--)
        {
            // left
            {
                int prel=li?pos[li-1]:-1;
                int w=pos[li]-prel;
                vector<p32> nop;
                // two-pointers
                {
                    auto nvec=li?cmd[li-1]:vector<ope>();
                    auto itr=begin(nvec);
                    for(auto x:cmd[li])
                    {
                        while(itr!=end(nvec) and itr->time<x.time)
                        {
                            nop.emplace_back(0,itr->dir);
                            ++itr;
                        }
                        nop.emplace_back(1,x.dir);
                    }
                    while(itr!=end(nvec))
                    {
                        nop.emplace_back(0,itr->dir);
                        ++itr;
                    }
                }

                vector<int> acc(nop.size());
                for(int i=0,prv=0; i<(int)nop.size(); ++i)
                {
                    if(nop[i].first)
                    {
                        acc[i]=prv-1;
                    }
                    else
                    {
                        acc[i]=prv+nop[i].second;
                    }
                    prv=acc[i];
                }
                vector<int> sufx(nop.size());
                for(int i=nop.size(),prv=0; i--; )
                {
                    prv=sufx[i]=max(acc[i],prv);
                }
                if(!sufx.empty() and sufx[0]>=w)
                {
                    cout << "NO" << "\n";
                    // cerr << "at left!\n";
                    return;
                }

                for(int i=0,cor=0,j=0; i<(int)nop.size(); ++i)
                {
                    if(nop[i].first)
                    {
                        int& ndir=cmd[li][j++].dir;
                        if(sufx[i]+2+cor<w)
                        {
                            cor+=2;
                            ndir=-1;
                        }
                    }
                }
            }
            // end left

            if(li==ri) continue;

            // right
            {
                int prer=ri<m-1?pos[ri+1]:n;
                int w=prer-pos[ri];
                vector<p32> nop;
                // two-pointers
                {
                    auto nvec=ri<m-1?cmd[ri+1]:vector<ope>();
                    auto itr=begin(nvec);
                    for(auto x:cmd[ri])
                    {
                        while(itr!=end(nvec) and itr->time<x.time)
                        {
                            nop.emplace_back(0,itr->dir);
                            ++itr;
                        }
                        nop.emplace_back(1,x.dir);
                    }
                    while(itr!=end(nvec))
                    {
                        nop.emplace_back(0,itr->dir);
                        ++itr;
                    }
                }

                vector<int> acc(nop.size());
                for(int i=0,prv=0; i<(int)nop.size(); ++i)
                {
                    if(nop[i].first)
                    {
                        acc[i]=prv-1;
                    }
                    else
                    {
                        acc[i]=prv+nop[i].second;
                    }
                    prv=acc[i];
                }
                vector<int> sufx(nop.size());
                for(int i=nop.size(),prv=0; i--; )
                {
                    prv=sufx[i]=max(acc[i],prv);
                }
                if(!sufx.empty() and sufx[0]>=w)
                {
                    cout << "NO" << "\n";
                    // cerr << "at right!\n";
                    return;
                }

                for(int i=0,cor=0,j=0; i<(int)nop.size(); ++i)
                {
                    if(nop[i].first)
                    {
                        int& ndir=cmd[ri][j++].dir;
                        if(sufx[i]+2+cor<w)
                        {
                            cor+=2;
                            ndir=-1;
                        }
                    }
                }
            }
            // end right
        }

        li--,ri++;
        if(li==ri) ++ri;

        // check center
        {
            auto litr=cmd[li].begin(),ritr=cmd[ri].begin();
            int nlpos=pos[li],nrpos=pos[ri];
            while(true)
            {
                if(litr==end(cmd[li]))
                {
                    if(ritr==end(cmd[ri]))
                    {
                        break;
                    }
                    nrpos-=ritr->dir;
                    ritr++;
                }
                else if(ritr==end(cmd[ri]))
                {
                    nlpos+=litr->dir;
                    litr++;
                }
                else
                {
                    if(litr->time<ritr->time)
                    {
                        nlpos+=litr->dir;
                        litr++;
                    }
                    else
                    {
                        nrpos-=ritr->dir;
                        ritr++;
                    }
                }
                if(nlpos==nrpos)
                {
                    cout << "NO" << "\n";
                    // cerr << "at center!\n";
                    return;
                }
            }
        }
*/
        cout << "YES" << "\n";
    }
};

yukicoder

結果

テストケース

ソースコード