結果

問題 No.5011 Better Mo's Algorithm is Needed!! (Weighted)
ユーザー tomeruntomerun
提出日時 2022-12-17 20:27:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4,948 ms / 5,000 ms
コード長 12,088 bytes
コンパイル時間 2,993 ms
実行使用メモリ 86,624 KB
スコア 42,826,162,644
最終ジャッジ日時 2022-12-17 20:38:28
合計ジャッジ時間 658,933 ms
ジャッジサーバーID
（参考情報） 		judge16 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4,929 ms
86,180 KB
testcase_01 AC 4,937 ms
86,112 KB
testcase_02 AC 4,933 ms
86,432 KB
testcase_03 AC 4,927 ms
86,264 KB
testcase_04 AC 4,927 ms
86,144 KB
testcase_05 AC 4,940 ms
86,344 KB
testcase_06 AC 4,933 ms
86,144 KB
testcase_07 AC 4,937 ms
86,108 KB
testcase_08 AC 4,931 ms
86,452 KB
testcase_09 AC 4,923 ms
86,164 KB
testcase_10 AC 4,929 ms
86,112 KB
testcase_11 AC 4,925 ms
86,308 KB
testcase_12 AC 4,925 ms
86,224 KB
testcase_13 AC 4,939 ms
86,124 KB
testcase_14 AC 4,934 ms
86,416 KB
testcase_15 AC 4,924 ms
86,164 KB
testcase_16 AC 4,930 ms
86,156 KB
testcase_17 AC 4,933 ms
86,344 KB
testcase_18 AC 4,947 ms
86,348 KB
testcase_19 AC 4,944 ms
86,256 KB
testcase_20 AC 4,936 ms
86,492 KB
testcase_21 AC 4,925 ms
86,144 KB
testcase_22 AC 4,927 ms
86,232 KB
testcase_23 AC 4,928 ms
86,428 KB
testcase_24 AC 4,945 ms
86,264 KB
testcase_25 AC 4,922 ms
86,056 KB
testcase_26 AC 4,947 ms
86,480 KB
testcase_27 AC 4,937 ms
86,024 KB
testcase_28 AC 4,924 ms
86,244 KB
testcase_29 AC 4,944 ms
86,256 KB
testcase_30 AC 4,927 ms
86,268 KB
testcase_31 AC 4,938 ms
86,176 KB
testcase_32 AC 4,948 ms
86,480 KB
testcase_33 AC 4,930 ms
86,284 KB
testcase_34 AC 4,928 ms
86,272 KB
testcase_35 AC 4,928 ms
86,424 KB
testcase_36 AC 4,940 ms
86,180 KB
testcase_37 AC 4,933 ms
86,200 KB
testcase_38 AC 4,935 ms
86,472 KB
testcase_39 AC 4,938 ms
86,332 KB
testcase_40 AC 4,941 ms
86,304 KB
testcase_41 AC 4,937 ms
86,444 KB
testcase_42 AC 4,928 ms
86,076 KB
testcase_43 AC 4,929 ms
86,040 KB
testcase_44 AC 4,930 ms
86,404 KB
testcase_45 AC 4,927 ms
86,296 KB
testcase_46 AC 4,934 ms
86,300 KB
testcase_47 AC 4,938 ms
86,556 KB
testcase_48 AC 4,926 ms
86,032 KB
testcase_49 AC 4,925 ms
86,296 KB
testcase_50 AC 4,923 ms
86,404 KB
testcase_51 AC 4,931 ms
86,024 KB
testcase_52 AC 4,927 ms
86,032 KB
testcase_53 AC 4,924 ms
86,564 KB
testcase_54 AC 4,928 ms
86,328 KB
testcase_55 AC 4,930 ms
86,288 KB
testcase_56 AC 4,928 ms
86,484 KB
testcase_57 AC 4,933 ms
86,208 KB
testcase_58 AC 4,942 ms
86,276 KB
testcase_59 AC 4,932 ms
86,540 KB
testcase_60 AC 4,930 ms
86,336 KB
testcase_61 AC 4,929 ms
85,992 KB
testcase_62 AC 4,929 ms
86,492 KB
testcase_63 AC 4,937 ms
86,212 KB
testcase_64 AC 4,928 ms
86,324 KB
testcase_65 AC 4,923 ms
86,472 KB
testcase_66 AC 4,932 ms
85,928 KB
testcase_67 AC 4,932 ms
86,384 KB
testcase_68 AC 4,925 ms
86,624 KB
testcase_69 AC 4,929 ms
86,232 KB
testcase_70 AC 4,935 ms
86,216 KB
testcase_71 AC 4,924 ms
86,468 KB
testcase_72 AC 4,931 ms
86,252 KB
testcase_73 AC 4,933 ms
86,388 KB
testcase_74 AC 4,926 ms
86,404 KB
testcase_75 AC 4,934 ms
86,320 KB
testcase_76 AC 4,933 ms
86,264 KB
testcase_77 AC 4,944 ms
86,492 KB
testcase_78 AC 4,938 ms
86,276 KB
testcase_79 AC 4,929 ms
86,132 KB
testcase_80 AC 4,925 ms
86,480 KB
testcase_81 AC 4,937 ms
86,216 KB
testcase_82 AC 4,927 ms
86,396 KB
testcase_83 AC 4,930 ms
86,512 KB
testcase_84 AC 4,935 ms
86,368 KB
testcase_85 AC 4,925 ms
86,036 KB
testcase_86 AC 4,925 ms
86,572 KB
testcase_87 AC 4,927 ms
86,036 KB
testcase_88 AC 4,925 ms
86,064 KB
testcase_89 AC 4,937 ms
86,456 KB
testcase_90 AC 4,928 ms
86,196 KB
testcase_91 AC 4,939 ms
86,272 KB
testcase_92 AC 4,930 ms
86,460 KB
testcase_93 AC 4,925 ms
86,284 KB
testcase_94 AC 4,928 ms
86,316 KB
testcase_95 AC 4,922 ms
86,460 KB
testcase_96 AC 4,927 ms
86,392 KB
testcase_97 AC 4,924 ms
86,200 KB
testcase_98 AC 4,940 ms
86,388 KB
testcase_99 AC 4,935 ms
86,268 KB
testcase_100 AC 4,931 ms
86,268 KB
testcase_101 AC 4,924 ms
86,548 KB
testcase_102 AC 4,931 ms
86,272 KB
testcase_103 AC 4,932 ms
86,232 KB
testcase_104 AC 4,926 ms
86,384 KB
testcase_105 AC 4,943 ms
86,020 KB
testcase_106 AC 4,925 ms
86,160 KB
testcase_107 AC 4,923 ms
86,364 KB
testcase_108 AC 4,928 ms
85,996 KB
testcase_109 AC 4,931 ms
86,284 KB
testcase_110 AC 4,922 ms
86,476 KB
testcase_111 AC 4,924 ms
86,300 KB
testcase_112 AC 4,925 ms
86,156 KB
testcase_113 AC 4,937 ms
86,424 KB
testcase_114 AC 4,941 ms
86,132 KB
testcase_115 AC 4,934 ms
86,128 KB
testcase_116 AC 4,922 ms
86,260 KB
testcase_117 AC 4,924 ms
86,056 KB
testcase_118 AC 4,926 ms
86,200 KB
testcase_119 AC 4,929 ms
86,476 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <utility>
#include <vector>
#include <iostream>
#include <array>
#include <numeric>
#include <memory>
#include <functional>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <sys/time.h>

#ifdef LOCAL
#ifndef NDEBUG
#define MEASURE_TIME
#define DEBUG
#endif
#else
#define NDEBUG
// #define DEBUG
#endif
#include <cassert>

using namespace std;
using u8=uint8_t;
using u16=uint16_t;
using u32=uint32_t;
using u64=uint64_t;
using i64=int64_t;
using ll=int64_t;
using ull=uint64_t;
using vi=vector<int>;
using vvi=vector<vi>;

namespace {

constexpr ll TL = 4900;

inline ll get_time() {
  struct timeval tv;
  gettimeofday(&tv, NULL);
  ll result =  tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;
  return result;
}

const ll start_time = get_time(); // msec

inline ll get_elapsed_msec() {
  return get_time() - start_time;
}

inline bool reach_time_limit() {
  return get_elapsed_msec() >= TL;
}

struct XorShift {
  uint32_t x,y,z,w;
  static const double TO_DOUBLE;

  XorShift() {
    x = 123456789;
    y = 362436069;
    z = 521288629;
    w = 88675123;
  }

  uint32_t nextUInt(uint32_t n) {
    uint32_t t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    return w % n;
  }

  uint32_t nextUInt() {
    uint32_t t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
  }

  double nextDouble() {
    return nextUInt() * TO_DOUBLE;
  }
};
const double XorShift::TO_DOUBLE = 1.0 / (1LL << 32);

struct Counter {
  vector<ull> cnt;

  void add(int i) {
    if (i >= cnt.size()) {
      cnt.resize(i+1);
    }
    ++cnt[i];
  }

  void print() {
    cerr << "counter:[";
    for (int i = 0; i < cnt.size(); ++i) {
      cerr << cnt[i] << ", ";
      if (i % 10 == 9) cerr << endl;
    }
    cerr << "]" << endl;
  }
};

struct Timer {
  vector<ull> at;
  vector<ull> sum;

  void start(int i) {
    if (i >= at.size()) {
      at.resize(i+1);
      sum.resize(i+1);
    }
    at[i] = get_time();
  }

  void stop(int i) {
    sum[i] += get_time() - at[i];
  }

  void print() {
    cerr << "timer:[";
    for (int i = 0; i < at.size(); ++i) {
      cerr << sum[i] << ", ";
      if (i % 10 == 9) cerr << endl;
    }
    cerr << "]" << endl;
  }
};

}

#ifdef MEASURE_TIME
#define START_TIMER(i) (timer.start(i))
#define STOP_TIMER(i) (timer.stop(i))
#define PRINT_TIMER() (timer.print())
#define ADD_COUNTER(i) (counter.add(i))
#define PRINT_COUNTER() (counter.print())
#else
#define START_TIMER(i)
#define STOP_TIMER(i)
#define PRINT_TIMER()
#define ADD_COUNTER(i)
#define PRINT_COUNTER()
#endif

#ifdef DEBUG
#define debug(format, ...) fprintf(stderr, format, __VA_ARGS__)
#define debugStr(str) fprintf(stderr, str)
#define debugln() fprintf(stderr, "\n")
#else
#define debug(format, ...)
#define debugStr(str)
#define debugln()
#endif

template<class T>
constexpr inline T sq(T v) { return v * v; }

void debug_vec(const vi& vec) {
  debugStr("[");
  for (int i = 0; i < vec.size(); ++i) {
    debug("%d ", vec[i]);
  }
  debugStr("]");
}

XorShift rnd;
Timer timer;
Counter counter;

//////// end of template ////////

constexpr int N = 200000;
constexpr int Q = 200000;
constexpr ll INF = 1ll << 62;
int WT, ST;
array<int64_t, N> W;
array<int64_t, N + 1> WS;
array<int, Q> L;
array<int, Q> R;
constexpr int PART = 51;

constexpr int DP_BIT = 3;
constexpr int DP_SKIP = -1;
ll dp[Q + 1][1 << DP_BIT][DP_BIT];
ll dp_prev[Q + 1][1 << DP_BIT][DP_BIT];

ll calc_cost(int l0, int r0, int l1, int r1) {
    ll cost = WS[max(l0, l1)] - WS[min(l0, l1)];
    cost += WS[max(r0, r1) + 1] - WS[min(r0, r1) + 1];
    return cost;
}

vi solve_dp(const vvi& buckets) {
    for (int i = 0; i < Q; ++i) {
        for (int j = 0; j < (1 << DP_BIT); ++j) {
            fill(dp[i][j], dp[i][j] + DP_BIT, INF);
        }
    }
    vi ranges = buckets[0];
    for (int i = 1; i < PART; ++i) {
        ranges.insert(ranges.end(), buckets[i].begin(), buckets[i].end());
    }
    for (int i = 0; i < DP_BIT; ++i) {
        dp[0][1 << i][i] = WS[R[ranges[0]] + 1] - WS[L[ranges[0]]];
    }
    for (int j = 0; j < (1 << DP_BIT); ++j) {
        int pk = j;
        while (pk) {
            int k = __builtin_ctz(pk);
            pk &= pk - 1;
            int left = L[ranges[k]];
            int right = R[ranges[k]];
            int nl = ((1 << DP_BIT) - 1) ^ j;
            while (nl) {
                int l = __builtin_ctz(nl);
                nl &= nl - 1;
                int left1 = L[ranges[l]];
                int right1 = R[ranges[l]];
                ll cost = WS[max(left, left1)] - WS[min(left, left1)];
                cost += WS[max(right, right1) + 1] - WS[min(right, right1) + 1];
                int next_bit = j | (1 << l);
                if (dp[0][next_bit][l] > dp[0][j][k] + cost) {
                    dp[0][next_bit][l] = dp[0][j][k] + cost;
                    dp_prev[0][next_bit][l] = k;
                    if ((j & 1) && l > 0 && dp[1][next_bit >> 1][l - 1] > dp[0][next_bit][l]) {
                        dp[1][next_bit >> 1][l - 1] = dp[0][next_bit][l];
                        dp_prev[1][next_bit >> 1][l - 1] = DP_SKIP;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= Q - DP_BIT; ++i) {
        for (int j = 0; j < (1 << (DP_BIT - 1)); ++j) {
            int pk = j;
            while (pk) {
                int k = __builtin_ctz(pk);
                pk &= pk - 1;
                if ((j & 1) && k > 0 && dp[i + 1][j >> 1][k - 1] > dp[i][j][k]) {
                    dp[i + 1][j >> 1][k - 1] = dp[i][j][k];
                    dp_prev[i + 1][j >> 1][k - 1] = DP_SKIP;
                }
                int left = L[ranges[i + k]];
                int right = R[ranges[i + k]];
                int l = DP_BIT - 1;
                int left1 = L[ranges[i + l]];
                int right1 = R[ranges[i + l]];
                ll cost = WS[max(left, left1)] - WS[min(left, left1)];
                cost += WS[max(right, right1) + 1] - WS[min(right, right1) + 1];
                int next_bit = j | (1 << l);
                if (dp[i][next_bit][l] > dp[i][j][k] + cost) {
                    dp[i][next_bit][l] = dp[i][j][k] + cost;
                    dp_prev[i][next_bit][l] = k;
                }
                if ((j & 1) && dp[i + 1][next_bit >> 1][l - 1] > dp[i][next_bit][l]) {
                    dp[i + 1][next_bit >> 1][l - 1] = dp[i][next_bit][l];
                    dp_prev[i + 1][next_bit >> 1][l - 1] = DP_SKIP;
                }
            }
        }

        for (int j = (1 << (DP_BIT - 1)); j < (1 << DP_BIT); ++j) {
            int pk = j;
            while (pk) {
                int k = __builtin_ctz(pk);
                pk &= pk - 1;
                int left = L[ranges[i + k]];
                int right = R[ranges[i + k]];
                int nl = ((1 << DP_BIT) - 1) ^ j;
                while (nl) {
                    int l = __builtin_ctz(nl);
                    nl &= nl - 1;
                    int left1 = L[ranges[i + l]];
                    int right1 = R[ranges[i + l]];
                    ll cost = WS[max(left, left1)] - WS[min(left, left1)];
                    cost += WS[max(right, right1) + 1] - WS[min(right, right1) + 1];
                    int next_bit = j | (1 << l);
                    if (dp[i][next_bit][l] > dp[i][j][k] + cost) {
                        dp[i][next_bit][l] = dp[i][j][k] + cost;
                        dp_prev[i][next_bit][l] = k;
                    }
                    if ((j & 1) && dp[i + 1][next_bit >> 1][l - 1] > dp[i][next_bit][l]) {
                        dp[i + 1][next_bit >> 1][l - 1] = dp[i][next_bit][l];
                        dp_prev[i + 1][next_bit >> 1][l - 1] = DP_SKIP;
                    }
                }
            }
        }

        // if (i > Q - DP_BIT - 3) {
        //     debug("i:%d\n", i);
        //     for (int j = 0; j < 1 << DP_BIT; ++j) {
        //         for (int k = 0; k < DP_BIT; ++k) {
        //             debug("%d %d %lld\n", j, k, dp[i][j][k]);
        //         }
        //     }
        // }
    }

    int best_k = 0;
    for (int i = 0; i < DP_BIT; ++i) {
        if (dp[Q - DP_BIT][(1 << DP_BIT) - 1][i] < dp[Q - DP_BIT][(1 << DP_BIT) - 1][best_k]) {
            best_k = i;
        }
    }
    debug("best_cost:%lld\n", dp[Q - DP_BIT][(1 << DP_BIT) - 1][best_k]);
    vi ans;
    int ci = Q - DP_BIT;
    int cj = (1 << DP_BIT) - 1;
    int k = best_k;
    ans.push_back(ranges[ci + k]);
    while (ci > 0 || cj > 0) {
        int prev = dp_prev[ci][cj][k];
        if (prev == DP_SKIP) {
            ci--;
            cj = (cj << 1) | 1;
            k++;
            // debugln();
        } else {
            // debug("%d\n", prev);
            assert(cj | (1 << prev));
            ans.push_back(ranges[ci + prev]);
            cj ^= 1 << k;
            k = prev;
        }
    }
    ans.pop_back();
    reverse(ans.begin(), ans.end());
    assert(ans.size() == Q);
    return ans;
}

bool accept(ll diff, double cooler) {
    if (diff <= 0) return true;
    double v = -diff * cooler;
    if (v < -9) return false;
    return rnd.nextDouble() < exp(v);
}

void solve_tsp(vi& ans) {
    constexpr int RANGE = 300;
    ll diff_sum = 0;
    int turn = 0;
    double cooler = 0.0005;
    while (true) {
        for (int i = 0; i < Q; ++i) {
            if ((i & 0xFFF) == 0) {
                ll elapsed = get_time() - start_time;
                if (elapsed > TL) {
                    debug("turn:%d %d diff_sum:%lld\n", turn, i, diff_sum);
                    return;
                }
            }
            int j = i + 2;
            int l00 = L[ans[i]];
            int r00 = R[ans[i]];
            int l01 = L[ans[i + 1]];
            int r01 = R[ans[i + 1]];
            ll diff_base = -calc_cost(l00, r00, l01, r01);
            for (int j = i + 2; j < i + RANGE && j < Q; ++j) {
                int l10 = L[ans[j]];
                int r10 = R[ans[j]];
                int l11 = L[ans[j + 1]];
                int r11 = R[ans[j + 1]];
                ll diff = diff_base - calc_cost(l10, r10, l11, r11);
                diff += calc_cost(l00, r00, l10, r10);
                diff += calc_cost(l01, r01, l11, r11);
                if (accept(diff, cooler)) {
                    diff_sum += diff;
                    reverse(ans.begin() + i + 1, ans.begin() + j + 1);
                    l01 = L[ans[i + 1]];
                    r01 = R[ans[i + 1]];
                    diff_base = -calc_cost(l00, r00, l01, r01);
                }
            }
        }
        debug("diff_sum:%lld\n", diff_sum);
        turn += 1;
        cooler *= 3;
    }
}

int main() {
    int _;
    scanf("%d %d %d %d", &_, &_, &WT, &ST);
    for (int i = 0; i < N; ++i) {
        scanf("%lld", &W[i]);
        WS[i + 1] = WS[i] + W[i];
    }
    for (int i = 0; i < Q; ++i) {
        scanf("%d %d", &L[i], &R[i]);
        L[i]--;
        R[i]--;
    }
    vector<vector<int>> buckets(PART);
    for (int i = 0; i < Q; ++i) {
        buckets[(ll)L[i] * PART / N].push_back(i);
    }
    for (int i = 0; i < PART; ++i) {
        if (i & 1) {
            sort(buckets[i].begin(), buckets[i].end(), [](int p0, int p1){
                return R[p0] > R[p1];
            });
        } else {
            sort(buckets[i].begin(), buckets[i].end(), [](int p0, int p1){
                return R[p0] < R[p1];
            });
        }
    }
    vi ans = solve_dp(buckets);
    solve_tsp(ans);
    int left = L[ans[0]];
    int right = R[ans[0]];
    ll ans_w = WS[right + 1] - WS[left];
    for (int i = 1; i < Q; ++i) {
        int left1 = L[ans[i]];
        int right1 = R[ans[i]];
        ans_w += WS[max(left, left1)] - WS[min(left, left1)];
        ans_w += WS[max(right, right1) + 1] - WS[min(right, right1) + 1];
        left = left1;
        right = right1;
    }
    debug("ans_w=%lld\n", ans_w);
    debug("score=%lld\n", (ll)round(1000000000000000000ll / ans_w));
    for (int p : ans) {
        printf("%d ", p + 1);
    }
    printf("\n");
}
0