結果
| 問題 |
No.5011 Better Mo's Algorithm is Needed!! (Weighted)
|
| コンテスト | |
| ユーザー |
 t33f
|
| 提出日時 | 2022-12-18 01:05:17 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 4,975 ms / 5,000 ms |
| コード長 | 6,756 bytes |
| コンパイル時間 | 1,272 ms |
| 実行使用メモリ | 11,196 KB |
| スコア | 128,822,228 |
| 最終ジャッジ日時 | 2022-12-18 01:16:06 |
| 合計ジャッジ時間 | 647,298 ms |
|
ジャッジサーバーID （参考情報） |
judge16 / judge10 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 120 |
ソースコード
#include <cmath>
#include <chrono>
#include <cassert>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <array>
#include <numeric>
#include <cstdio>
#include <iostream>
using namespace std;
unsigned int xor128() {
static unsigned int x=123456789, y=362436069, z=521288629, w=88675123;
unsigned int t;
t=(x^(x<<11)); x=y; y=z; z=w;
return (w=(w^(w>>19))^(t^(t>>8)));
}
inline bool rand_bool(double prob) {
constexpr double x = 1LL<<32; // uint_max+1
return xor128() < prob * x;
}
inline int rand_int(int n) { return xor128()%n; }
int timelimit = 5 * 1000, margin = 50;
class Timer {
chrono::system_clock::time_point start_time = chrono::system_clock::now();
public:
Timer() {}
long long get_elapsed_time() {
auto diff = chrono::system_clock::now() - start_time;
return chrono::duration_cast<chrono::milliseconds>(diff).count();
}
} timer;
constexpr int N = 200000, Q = 200000;
int WT, ST;
int W[N], L[Q], R[Q];
int Wsum[N + 1]; // sum of [0, i)
int LWsum[N], RWsum[N];
long long initial_cost(int i) {
return Wsum[R[i] + 1] - Wsum[L[i]];
}
long long adj_cost(int i, int j) {
return abs(LWsum[i] - LWsum[j]) + abs(RWsum[i] - RWsum[j]);
}
long long calc_cost(const array<int, Q> &ans) {
long long c = initial_cost(ans[0]);
for (int i = 1; i < Q; ++i) c += adj_cost(ans[i - 1], ans[i]);
return c;
}
long long score_of_cost(long long cost) {
constexpr long long n = (long long)1e18;
return n % cost * 2 >= cost ? n / cost + 1 : n / cost;
}
void read_input() {
/* scanf("%*d %*d %d %d", &WT, &ST); */
/* for (int i = 0; i < N; i++) scanf(" %d", W + i); */
/* for (int i = 0; i < Q; i++) scanf(" %d %d", L + i, R + i), L[i]--, R[i]--; */
/* Wsum[0] = 0; */
/* for (int i = 0; i < N; i++) Wsum[i + 1] = Wsum[i] + W[i]; */
WT = 2;
ST = 1;
for (int i = 0; i < N; i++) W[i] = 1 + rand_int(100);
for (int i = 0; i < Q; i++) {
L[i] = rand_int(N);
R[i] = rand_int(N);
if (L[i] > R[i]) swap(L[i], R[i]);
}
Wsum[0] = 0;
for (int i = 0; i < N; i++) Wsum[i + 1] = Wsum[i] + W[i];
for (int i = 0; i < Q; i++) {
LWsum[i] = Wsum[L[i]];
RWsum[i] = Wsum[R[i] + 1];
}
}
vector<vector<int>> partition_queries(int B) {
if (WT == 4 || ST == 2) {
array<int, N> start_count;
for (int i = 0; i < Q; ++i) start_count[L[i]]++;
vector<int> boundaries;
long long w1 = 0, w2 = Wsum[N];
long long s = 0;
const int bias = WT == 4 ? 20 : 40;
for (int i = 0; i < N; ++i) {
s += start_count[i];
w1 += s * W[i];
w2 -= W[i];
if (w1 > w2 * bias) {
boundaries.push_back(i);
s = 0;
w1 = 0;
//cerr << "boundary " << i << endl;
}
}
vector<vector<int>> buckets(boundaries.size() + 1);
boundaries.push_back(N); // sentinel
for (int i = 0; i < Q; ++i) {
auto it = lower_bound(boundaries.begin(), boundaries.end(), L[i]);
const size_t j = it - boundaries.begin();
buckets[j].push_back(i);
}
return buckets;
} else {
array<int, N> a;
iota(a.begin(), a.end(), 0);
vector<vector<int>> buckets((N + B - 1) / B + 1);
for (int i = 0; i < Q; i++) {
const int b = L[i] / B;
buckets[b].push_back(i);
}
return buckets;
}
}
array<int, Q> initial_solution(int B) {
vector<vector<int>> buckets = partition_queries(B);
array<int, Q> ans;
int pos = 0;
for (int b = 0; b < buckets.size(); ++b) {
vector<int> &elems = buckets[b];
sort(elems.begin(), elems.end(), [b](int i, int j) {
if (b % 2 == 0) return make_pair(R[i], L[i]) < make_pair(R[j], L[j]);
else return make_pair(R[i], L[i]) > make_pair(R[j], L[j]);
});
for (int i : elems) ans[pos++] = i;
}
return ans;
}
array<int, Q> solve(int B, int S) {
array<int, Q> ans = initial_solution(B);
long long cur_cost = calc_cost(ans);
long long best_cost = cur_cost;
array<int, Q> best_ans = ans;
const double start_temp = cur_cost / N * 0.15, end_temp = 0;
const int upd_interval = 10;
long long next_upd = timelimit - margin - 10 * upd_interval;
for (;;) {
cerr << cur_cost << ' ' << score_of_cost(cur_cost) << endl;
for (int i = 0; i < N; ++i) {
const long long elapsed = timer.get_elapsed_time();
const bool finish = (elapsed + margin > timelimit);
const bool check_update = (finish || next_upd < elapsed);
// best_ans の更新がボトルネックになるので毎回更新しないで
// 最後の方だけ一定時間ごとに現在のスコアを見て、改善していたら更新
if (check_update && cur_cost < best_cost) {
next_upd += upd_interval;
best_cost = cur_cost;
best_ans = ans;
}
if (finish) {
if (initial_cost(best_ans.front()) > initial_cost(best_ans.back()))
reverse(best_ans.begin(), best_ans.end());
return best_ans;
}
const double progress = double(elapsed) / timelimit,
temp = start_temp + (end_temp - start_temp) * progress;
const int jmax = min(N, i + S);
for (int j = i + 1; j < jmax; ++j) {
long long diff = 0;
if (i > 0) {
diff -= adj_cost(ans[i - 1], ans[i]);
diff += adj_cost(ans[i - 1], ans[j]);
} else {
diff -= initial_cost(ans[0]);
diff += initial_cost(ans[j]);
}
if (j + 1 < N) {
diff -= adj_cost(ans[j], ans[j + 1]);
diff += adj_cost(ans[i], ans[j + 1]);
}
bool accept = (diff <= 0);
if (!accept && diff < temp * 3) {
double prob = exp(-diff / temp);
accept = rand_bool(prob);
}
if (accept) {
reverse(ans.begin() + i, ans.begin() + j + 1);
cur_cost += diff;
}
}
}
}
}
int main(int argc, char **argv) {
read_input();
const int B = argc <= 1 ? 3500 : atoi(argv[1]);
const int S = argc <= 2 ? 100 : atoi(argv[2]);
const array<int, Q> ans = solve(B, S);
for (int i : ans) cout << i + 1 << ' ';
cout << endl;
cerr << "score = " << score_of_cost(calc_cost(ans)) << endl;
}