結果
| 問題 | No.2596 Christmas Eve (Heuristic ver.) |
| コンテスト | |
| ユーザー |
 syndrome
|
| 提出日時 | 2025-11-26 00:39:12 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,119 ms / 1,224 ms |
| コード長 | 9,252 bytes |
| 記録 | |
| コンパイル時間 | 3,114 ms |
| コンパイル使用メモリ | 254,856 KB |
| 実行使用メモリ | 12,172 KB |
| スコア | 5,000,000 |
| 最終ジャッジ日時 | 2025-11-26 00:41:46 |
| 合計ジャッジ時間 | 152,269 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 125 |
ソースコード
// (◕ᴗ◕✿)
// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define srep(i, s, n) for (ll i = s; i < (n); ++i)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>;
using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>;
using uint = unsigned int;
using ull = unsigned long long;
const ld pi = 3.141592653589793;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1000000007;
const ll mod = 998244353;
#define debug(var) do { cout << #var << " :\n"; view(var); } while(0)
template<typename T>void view(const T& e) {cout << e;}
template<typename T1, typename T2>void view(const pair<T1, T2>& p) {cout << "{" << p.first << ", " << p.second << "}";}
template<typename T>void view(const vc<T>& v) {for (const auto& e : v) {view(e);cout << " ";} cout << endl;}
template<typename T>void view(const vv<T>& vv) {for (const auto& v : vv) {view(v);cout << " ";} cout << endl;}
template<typename T>void view(const set<T>& s) {for (const auto& e : s) {view(e);cout << " ";} cout << endl;}
template<typename T>void view(const unordered_set<T>& s) {for (const auto& e : s) {view(e);cout << " ";} cout << endl;}
template<typename T1, typename T2>void view(const map<T1, T2>& mp){for (const auto& e : mp) {view(e);cout << " ";} cout << endl;}
// #define DEBUG
#ifdef DEBUG
constexpr bool DEBUGMODE = true;
#else
constexpr bool DEBUGMODE = false;
#endif
ofstream wrt;
string outputfile = "output.txt", inputfile = "input.txt";
unsigned int randxor(){
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));
}
int randint(int a, int b) {return(a + randxor() % (b - a));}
struct Timer {
public:
Timer(int limit){
start = chrono::high_resolution_clock::now();
goal = start + chrono::milliseconds(limit);
}
inline double rate(){
return (chrono::high_resolution_clock::now() - start).count() / (double)(goal - start).count();
}
inline int get_time(){return (chrono::high_resolution_clock::now() - start).count() / 1e6;}
private:
chrono::high_resolution_clock::time_point start;
chrono::high_resolution_clock::time_point goal;
};
//variable
constexpr int TIME_LIMIT = 1100;
constexpr int N = 500;
constexpr ll coeff1 = 2 * N * 2 * N * N;
constexpr ll coeff2 = 2 * N * N;
constexpr ll coeff3 = N;
int K;
int A[N], B[N];
int C[2 * N], D[2 * N];
int E[N], F[N];
int P1[N], P2[2 * N], P3[N];
vi centers[2 * N];
bitset<N> use1, use3;
bitset<2 * N> use2;
struct Solver{
vc<pair<int, int>> candidates;
set<pair<int, ll>> trees;
ll sum = 0, sum2 = 0;
ll encode(int a, int c1, int c2, int e){
return a * coeff1 + c1 * coeff2 + c2 * coeff3 + e;
}
tuple<int, int, int, int> decode(ll x){
return {x / coeff1, x % coeff1 / coeff2, x % coeff2 / coeff3, x % coeff3};
}
void input(){
if (DEBUGMODE){
ifstream in(inputfile);
cin.rdbuf(in.rdbuf());
int a; cin >> a >> K;
rep(i, N) cin >> A[i];
rep(i, N) cin >> B[i];
rep(i, 2 * N) cin >> C[i];
rep(i, 2 * N) cin >> D[i];
rep(i, N) cin >> E[i];
rep(i, N) cin >> F[i];
}else{
int a; cin >> a >> K;
rep(i, N) cin >> A[i];
rep(i, N) cin >> B[i];
rep(i, 2 * N) cin >> C[i];
rep(i, 2 * N) cin >> D[i];
rep(i, N) cin >> E[i];
rep(i, N) cin >> F[i];
}
}
void init(){
iota(P1, P1 + N, 0);
sort(P1, P1 + N, [&](auto i, auto j){return A[i] < A[j];});
iota(P2, P2 + 2 * N, 0);
sort(P2, P2 + 2 * N, [&](auto i, auto j){return C[i] < C[j];});
rep(i, 2 * N){
rep(j, 2 * N) if (j != i && C[i] <= C[j]) centers[i].push_back(j);
sort(all(centers[i]), [&](auto a, auto b){return D[a] < D[b];});
}
iota(P3, P3 + N, 0);
sort(P3, P3 + N, [&](auto i, auto j){return E[i] < E[j];});
rep(i, N) rep(j, 2 * N) if (j != P2[2 * N - 1] && A[i] < C[j]) candidates.push_back({i, j});
}
pair<int, ll> FindGoodTree(pair<int, ll> &last){
double target = sum / (double)(K - 1);
pair<int, ll> best = last;
double bestscore = abs(target - best.first);
rep(i, 10){
int a, c1;
tie(a, c1) = candidates[randint(0, len(candidates))];
if (use1[a] || use2[c1]) continue;
for (auto& e : P3){
if (E[e] >= A[a]) break;
if (use3[e]) continue;
int h = B[a] + D[c1] + F[e];
int bottom = 0, top = len(centers[c1]);
while (top - bottom > 1){
int mid = (top + bottom) / 2;
if (target <= h + D[centers[c1][mid]]) top = mid;
else bottom = mid;
}
int l = bottom, r = top;
while (l > 0 && use2[centers[c1][l]]) l--;
while (r < len(centers[c1]) - 1 && use2[centers[c1][r]]) r++;
if (!use2[centers[c1][l]] && abs(h + D[centers[c1][l]] - target) < bestscore){
best = {h + D[centers[c1][l]], encode(a, c1, centers[c1][l], e)};
bestscore = abs(h + D[centers[c1][l]] - target);
}
if (r < len(centers[c1]) && !use2[centers[c1][r]] && abs(h + D[centers[c1][r]] - target) < bestscore){
best = {h + D[centers[c1][r]], encode(a, c1, centers[c1][r], e)};
bestscore = abs(h + D[centers[c1][r]] - target);
}
}
}
return best;
}
void HC(Timer &timer){
while (len(trees) < K){
int a, c1;
tie(a, c1) = candidates[randint(0, len(candidates))];
if (use1[a] || use2[c1]) continue;
int e = randint(0, N);
rep(i, 10) if (E[e] >= A[a] || use3[e]) e = randint(0, N);
if (E[e] >= A[a] || use3[e]) continue;
int c2 = centers[c1][randint(0, len(centers[c1]))];
rep(i, 10) if (use2[c2]) c2 = centers[c1][randint(0, len(centers[c1]))];
if (use2[c2]) continue;
int h = B[a] + D[c1] + D[c2] + F[e];
sum += h;
sum2 += h * h;
trees.insert({h, encode(a, c1, c2, e)});
use1.set(a);
use2.set(c1);
use2.set(c2);
use3.set(e);
}
int roop = 0;
while (++roop){
pair<int, ll> last;
if (randint(0, 2)){
auto it = trees.begin();
last = *it;
trees.erase(it);
}else{
auto it = trees.end(); it--;
last = *it;
trees.erase(it);
}
auto [h, t] = last;
sum -= h;
sum2 -= h * h;
auto [a_, c1_, c2_, e_] = decode(t);
use1.reset(a_);
use2.reset(c1_);
use2.reset(c2_);
use3.reset(e_);
auto best = FindGoodTree(last);
int nh = best.first;
auto [a, c1, c2, e] = decode(best.second);
sum += nh;
sum2 += nh * nh;
trees.insert(best);
// assert(!use1[a] && !use2[c1] && !use2[c2] && !use3[e]);
use1.set(a);
use2.set(c1);
use2.set(c2);
use3.set(e);
if (roop % 1000 == 0){
if (timer.rate() > 1.0) break;
}
}
cerr << "roop : " << roop << endl;
}
void output(){
cerr << sqrt(sum2 / (double)K - sum * sum / (double)(K * K)) << endl;
if (DEBUGMODE){
for (auto [h, t] : trees){
auto [a, c1, c2, e] = decode(t);
// if (A[a] <= E[e]) cout << "wrong ae" << endl;
// if (E[e] >= C[c1]) cout << "wrong ec1" << endl;
// if (E[e] >= C[c2]) cout << "wrong ec2 " << E[e] << ' ' << A[a] << ' ' << C[c1] << ' ' << C[c2] << endl;
wrt << a + 1 << ' ' << c1 + 1 << ' ' << c2 + 1 << ' ' << e + 1 << endl;
}
}else{
for (auto [h, t] : trees){
auto [a, c1, c2, e] = decode(t);
cout << a + 1 << ' ' << c1 + 1 << ' ' << c2 + 1 << ' ' << e + 1 << endl;
}
}
}
void run(){
Timer timer(TIME_LIMIT);
input();
init();
HC(timer);
output();
}
};
int main(){
wrt.open(outputfile, ios::out);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Solver solver;
solver.run();
wrt.close();
return 0;
}