#826263 (C++17) No.5012 Better Mo's Algorithm is Needed!! (Execute)

提出ソース

結果

問題	No.5012 Better Mo's Algorithm is Needed!! (Execute)
ユーザー	👑 Nachia
提出日時	2022-12-17 00:36:09
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	51 ms / 500 ms
コード長	5,103 bytes
コンパイル時間	1,145 ms
実行使用メモリ	7,920 KB
スコア	1,000,000,000,092,809,462
最終ジャッジ日時	2022-12-17 00:37:37
合計ジャッジ時間	84,177 ms
ジャッジサーバーID （参考情報）	judge15 / judge16
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 3,460 KB
testcase_01	AC	46 ms 7,680 KB
testcase_02	AC	49 ms 7,796 KB
testcase_03	AC	50 ms 7,800 KB
testcase_04	AC	49 ms 7,808 KB
testcase_05	AC	49 ms 7,708 KB
testcase_06	AC	50 ms 7,760 KB
testcase_07	AC	49 ms 7,800 KB
testcase_08	AC	50 ms 7,796 KB
testcase_09	AC	49 ms 7,712 KB
testcase_10	AC	49 ms 7,684 KB
testcase_11	AC	50 ms 7,752 KB
testcase_12	AC	50 ms 7,776 KB
testcase_13	AC	49 ms 7,760 KB
testcase_14	AC	50 ms 7,692 KB
testcase_15	AC	51 ms 7,704 KB
testcase_16	AC	49 ms 7,688 KB
testcase_17	AC	49 ms 7,676 KB
testcase_18	AC	49 ms 7,680 KB
testcase_19	AC	49 ms 7,756 KB
testcase_20	AC	50 ms 7,680 KB
testcase_21	AC	50 ms 7,728 KB
testcase_22	AC	6 ms 4,028 KB
testcase_23	AC	6 ms 3,856 KB
testcase_24	AC	6 ms 3,916 KB
testcase_25	AC	9 ms 4,016 KB
testcase_26	AC	9 ms 3,856 KB
testcase_27	AC	9 ms 3,996 KB
testcase_28	AC	21 ms 5,476 KB
testcase_29	AC	20 ms 5,308 KB
testcase_30	AC	20 ms 5,256 KB
testcase_31	AC	40 ms 7,444 KB
testcase_32	AC	40 ms 7,352 KB
testcase_33	AC	39 ms 7,568 KB
testcase_34	AC	7 ms 4,032 KB
testcase_35	AC	7 ms 3,992 KB
testcase_36	AC	7 ms 4,044 KB
testcase_37	AC	11 ms 4,164 KB
testcase_38	AC	11 ms 4,084 KB
testcase_39	AC	14 ms 4,156 KB
testcase_40	AC	22 ms 5,280 KB
testcase_41	AC	21 ms 5,344 KB
testcase_42	AC	22 ms 5,392 KB
testcase_43	AC	43 ms 7,364 KB
testcase_44	AC	43 ms 7,488 KB
testcase_45	AC	41 ms 7,396 KB
testcase_46	AC	10 ms 3,960 KB
testcase_47	AC	10 ms 4,100 KB
testcase_48	AC	10 ms 3,916 KB
testcase_49	AC	14 ms 4,184 KB
testcase_50	AC	14 ms 4,252 KB
testcase_51	AC	13 ms 4,396 KB
testcase_52	AC	25 ms 5,508 KB
testcase_53	AC	25 ms 5,484 KB
testcase_54	AC	25 ms 5,504 KB
testcase_55	AC	44 ms 7,516 KB
testcase_56	AC	45 ms 7,508 KB
testcase_57	AC	45 ms 7,508 KB
testcase_58	AC	15 ms 3,944 KB
testcase_59	AC	16 ms 4,148 KB
testcase_60	AC	15 ms 3,932 KB
testcase_61	AC	19 ms 4,340 KB
testcase_62	AC	19 ms 4,480 KB
testcase_63	AC	18 ms 4,476 KB
testcase_64	AC	29 ms 5,752 KB
testcase_65	AC	30 ms 5,704 KB
testcase_66	AC	29 ms 5,684 KB
testcase_67	AC	49 ms 7,844 KB
testcase_68	AC	49 ms 7,704 KB
testcase_69	AC	50 ms 7,764 KB
testcase_70	AC	49 ms 7,776 KB
testcase_71	AC	50 ms 7,712 KB
testcase_72	AC	48 ms 7,704 KB
testcase_73	AC	49 ms 7,808 KB
testcase_74	AC	50 ms 7,808 KB
testcase_75	AC	50 ms 7,796 KB
testcase_76	AC	50 ms 7,824 KB
testcase_77	AC	49 ms 7,724 KB
testcase_78	AC	49 ms 7,876 KB
testcase_79	AC	50 ms 7,756 KB
testcase_80	AC	50 ms 7,692 KB
testcase_81	AC	49 ms 7,764 KB
testcase_82	AC	49 ms 7,764 KB
testcase_83	AC	49 ms 7,820 KB
testcase_84	AC	49 ms 7,780 KB
testcase_85	AC	50 ms 7,812 KB
testcase_86	AC	49 ms 7,828 KB
testcase_87	AC	50 ms 7,804 KB
testcase_88	AC	50 ms 7,760 KB
testcase_89	AC	49 ms 7,696 KB
testcase_90	AC	50 ms 7,840 KB
testcase_91	AC	50 ms 7,840 KB
testcase_92	AC	50 ms 7,680 KB
testcase_93	AC	50 ms 7,808 KB
testcase_94	AC	50 ms 7,708 KB
testcase_95	AC	50 ms 7,764 KB
testcase_96	AC	50 ms 7,692 KB
testcase_97	AC	49 ms 7,920 KB
testcase_98	AC	49 ms 7,896 KB
testcase_99	AC	50 ms 7,764 KB

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

ソースコード

raw source code

#line 1 "Main.cpp"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <atcoder/modint>
#line 2 "nachia\\misc\\sorting.hpp"

#line 4 "nachia\\misc\\sorting.hpp"
#include <cassert>
#line 6 "nachia\\misc\\sorting.hpp"

namespace nachia{

template<class Iterator>
void EnsurePermutation(Iterator first, Iterator last){
    int n = std::distance(first, last);
    std::vector<int> vis(n, 0);
    for(Iterator i=first; i!=last; i++){
        assert(0 <= *i);
        assert(*i < n);
        assert(vis[*i] == 0);
        vis[*i] = 1;
    }
}

template<class T> std::vector<T> Permute(
    const std::vector<T>& src,
    const std::vector<int>& perm
){
    const bool DEBUG = true;
    int n = src.size();
    if constexpr (DEBUG){
        assert(perm.size() == src.size());
        EnsurePermutation(perm.begin(), perm.end());
    }
    std::vector<T> res;
    res.reserve(n);
    for(int i=0; i<n; i++) res.push_back(src[perm[i]]);
    return res;
}

template<class T> std::vector<T>& PermuteInPlace(
    std::vector<T>& src,
    std::vector<int> perm
){
    const bool DEBUG = true;
    int n = src.size();
    if constexpr (DEBUG){
        assert(perm.size() == src.size());
        EnsurePermutation(perm.begin(), perm.end());
    }
    for(int s=0; s<n; s++){
        int p = s;
        while(perm[p] != s){
            std::swap(src[p], src[perm[p]]);
            std::swap(p, perm[p]);
        }
        perm[p] = p;
    }
    return src;
}

// stable sort
std::vector<int> BucketSortPermutation(
    std::vector<int>::const_iterator first,
    std::vector<int>::const_iterator last,
    int maxVal
){
    const bool DEBUG = true;
    int n = last - first;
    if constexpr (DEBUG){
        for(auto itr = first; itr != last; itr++){
            assert(0 <= *itr);
            assert(*itr <= maxVal);
        }
    }
    std::vector<int> cnt(maxVal+2);
    std::vector<int> res(n);
    for(int i=0; i<n; i++) cnt[first[i]+1]++;
    for(int i=0; i<maxVal; i++) cnt[i+1] += cnt[i];
    for(int i=0; i<n; i++) res[cnt[first[i]]++] = i;
    return res;
}

// stable sort
template<class T, class Mapping>
std::vector<int> BucketSortPermutation(
    typename std::vector<T>::const_iterator first,
    typename std::vector<T>::const_iterator last,
    const Mapping& f,
    int maxVal
){
    std::vector<int> buf(last - first);
    auto bufitr = buf.begin();
    for(auto itr = first; itr != last; itr++, bufitr++) *bufitr = f(*itr);
    return BucketSortPermutation(buf.begin(), buf.end(), maxVal);
}

// stable sort
template<class T, class Mapping>
std::vector<T> BucketSort(
    std::vector<T> src,
    const Mapping& f,
    int maxVal
){
    return PermuteInPlace(src, BucketSortPermutation<T>(src.begin(), src.end(), f, maxVal));
}

// stable sort
template<class Iter, class Mapping>
std::vector<int> BucketSortPermutation(
    Iter first,
    Iter last,
    const Mapping& f,
    int maxVal
){
    std::vector<int> buf(std::distance(first, last));
    auto bufitr = buf.begin();
    for(auto itr = first; itr != last; itr++, bufitr++) *bufitr = f(*itr);
    return BucketSortPermutation(buf.begin(), buf.end(), maxVal);
}

template<class Iter> void PermuteInPlace(
    Iter srcFirst,
    Iter srcLast,
    std::vector<int> perm
){
    const bool DEBUG = true;
    int n = std::distance(srcFirst, srcLast);
    if constexpr (DEBUG){
        assert(perm.size() == (size_t)n);
        EnsurePermutation(perm.begin(), perm.end());
    }
    for(int s=0; s<n; s++){
        int p = s;
        while(perm[p] != s){
            std::swap(srcFirst[p], srcFirst[perm[p]]);
            std::swap(p, perm[p]);
        }
        perm[p] = p;
    }
}

// stable sort
template<class Iter, class Mapping>
void BucketSort(
    Iter destFirst,
    Iter destLast,
    const Mapping& f,
    int maxVal
){
    PermuteInPlace(destFirst, destLast, BucketSortPermutation(destFirst, destLast, f, maxVal));
}

}
#line 8 "Main.cpp"

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

using Modint = atcoder::static_modint<998244353>;


int main(){
    struct Range { int l, r, i; };
    int N, Q; cin >> N >> Q;
    vector<int> A(N); rep(i,N) cin >> A[i];
    vector<Range> G(Q);
    int sqrtN = 1; while(sqrtN * sqrtN <= N) sqrtN++;
    rep(i,Q){ G[i].i = i+1; cin >> G[i].l >> G[i].r; G[i].l--; }
    G = nachia::BucketSort(G, [&](Range g){ return g.r%2 ? g.l%sqrtN : sqrtN-g.l%sqrtN; }, sqrtN);
    G = nachia::BucketSort(G, [&](Range g){ return g.l/sqrtN%2 ? g.r%sqrtN : sqrtN-g.r%sqrtN; }, sqrtN);
    G = nachia::BucketSort(G, [&](Range g){ return g.r/sqrtN%2 ? g.l/sqrtN : sqrtN-g.l/sqrtN; }, sqrtN);
    G = nachia::BucketSort(G, [&](Range g){ return g.r/sqrtN; }, sqrtN);
    rep(i,Q){
        if(i) cout << ' ';
        cout << G[i].i;
    }
    cout << '\n';
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;

yukicoder

結果

テストケース

ソースコード