結果
| 問題 | No.5025 Forest Fire |
| コンテスト | |
| ユーザー |
 Nika Jimsheleishvili
|
| 提出日時 | 2026-10-24 17:34:24 |
| 言語 | C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1,941 ms / 2,000 ms |
| + 505µs | |
| コード長 | 26,695 bytes |
| 記録 | |
| コンパイル時間 | 3,621 ms |
| コンパイル使用メモリ | 274,004 KB |
| 実行使用メモリ | 9,928 KB |
| スコア | 187,196,990 |
| 最終ジャッジ日時 | 2026-10-24 17:47:54 |
| 合計ジャッジ時間 | 159,670 ms |
|
ジャッジサーバーID （参考情報） |
judge6_0 / <nil> |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
double TL = 1.95;
//#pragma GCC optimize("O3,Ofast,omit-frame-pointer,unroll-all-loops,tree-loop-vectorize,tree-slp-vectorize")
#include <algorithm>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
int STANDARD = 1;
using namespace std;
#define F0(i,n) for (int i=0; i<(n); i++)
#define F1(i,n) for (int i=1; i<=(n); i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define SZ(x) ((int)x.size())
const int inf = 1000000000;
const double pi = acos(-1.0);
typedef pair<int, int> pii;
typedef long long ll;
const double EPS = 1e-9;
istream& operator>>(istream& is, pii& p) { is>>p.first>>p.second; return is; }
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B>& p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<class A, class B, class C>
ostream& operator<<(ostream& os, const tuple<A, B, C>& p) { os << "(" << get<0>(p) << "," << get<1>(p) << "," << get<2>(p) << ")"; return os; }
template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "["; F0(i,SZ(v)) { if (i>0) os << ","; os << v[i]; } os << "]"; return os;
}
template<class T>
ostream& operator<<(ostream& os, const set<T>& v) {
os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ","; cerr << i; } os << "}"; return os;
}
template<class T, class R>
ostream& operator<<(ostream& os, const map<T,R>& v) {
os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ", "; cerr << i.first << ":" << i.second; } os << "}"; return os;
}
void print_all() { cerr << endl; }
template <typename H, typename... T>
void print_all(H head, T... tail) { cerr << " " << head; print_all(tail...); }
chrono::system_clock::time_point init_time = chrono::system_clock::now();
inline double GetSeconds() {
chrono::system_clock::time_point current_time = chrono::system_clock::now();
double ret = chrono::duration_cast<std::chrono::nanoseconds>(current_time - init_time).count();
return ret * 1e-9;
}
const int MAX_RAND = 1 << 30;
struct Rand {
ll x, y, z, w, o;
Rand() { throw; }
Rand(ll seed) { reseed(seed); o = 0; }
inline void reseed(ll seed) { x = 0x498b3bc5 ^ seed; y = 0; z = 0; w = 0; F0(i, 20) mix(); }
inline void mix() { ll t = x ^ (x << 11); x = y; y = z; z = w; w = w ^ (w >> 19) ^ t ^ (t >> 8); }
inline ll rand() { mix(); return x & (MAX_RAND - 1); }
inline ll zh() { mix(); return x; }
inline int nextInt(int n) { return rand() % n; }
inline int nextInt(int L, int R) { return rand()%(R - L + 1) + L; }
inline int nextBool() { if (o < 4) o = rand(); o >>= 2; return o & 1; }
inline double nextDouble() { return rand() * 1.0 / MAX_RAND; }
inline double nextDouble(double L, double R) { return L + (R - L) * nextDouble(); }
template<class T> auto REL(T& v) { return v[nextInt(SZ(v))]; }
template<class T> void RS(vector<T>& v) { F1(i, SZ(v)-1) { int j = nextInt(0, i); swap(v[i], v[j]); } }
int ws_n; vector<double> ws_prob; vector<int> ws_alias;
inline void PrepareWeightedSample(const vector<double>& p) {
ws_n = SZ(p); ws_prob.assign(ws_n, 0); ws_alias.assign(ws_n, 0);
vector<double> sc(ws_n);
vector<int> small, large;
double sum = 0; F0(i, ws_n) sum += p[i];
F0(i, ws_n) {
sc[i] = p[i]/sum * ws_n; if (sc[i] < 1) small.push_back(i); else large.push_back(i);
}
while(!small.empty() && !large.empty()){
int l = small.back(); small.pop_back();
int g = large.back(); large.pop_back();
ws_prob[l] = sc[l]; ws_alias[l] = g;
sc[g] = sc[g] - (1 - sc[l]);
if(sc[g] < 1) small.push_back(g); else large.push_back(g);
}
for(int g : large){ ws_prob[g]=1; ws_alias[g]=g; }
for(int l : small){ ws_prob[l]=1; ws_alias[l]=l; }
}
inline int WeightedSample() { int i = nextInt(ws_n); return nextDouble() < ws_prob[i] ? i : ws_alias[i]; }
};
Rand my(2023);
double saveTime;
double t_o[20];
ll c_o[20];
void Init() {
saveTime = GetSeconds();
F0(i, 20) t_o[i] = 0.0;
F0(i, 20) c_o[i] = 0;
}
double Elapsed() { return GetSeconds() - saveTime; }
void Report() {
double tmp = Elapsed();
cerr << "-------------------------------------" << endl;
cerr << "Elapsed time: " << tmp << " sec" << endl;
double total = 0.0; F0(i, 20) { if (t_o[i] > 0) cerr << "t_o[" << i << "] = " << t_o[i] << endl; total += t_o[i]; } cerr << endl; //if (total > 0) cerr << "Total spent: " << total << endl;
F0(i, 20) if (c_o[i] > 0) cerr << "c_o[" << i << "] = " << c_o[i] << endl;
cerr << "-------------------------------------" << endl;
}
#ifdef LOCAL
#define PR(...) cerr << #__VA_ARGS__ << " =", print_all(__VA_ARGS__)
struct AutoTimer {
int x;
double t;
AutoTimer(int x) : x(x) { t = Elapsed(); }
~AutoTimer() { t_o[x] += Elapsed() - t; }
};
#define AT(i) AutoTimer _a##i(i)
#else
//#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-all-loops")
#define PR(...)
#define AT(i)
#endif
// CONSTANTS
const int N = 50;
int n, k;
int d[N][N];
int W[N][N];
double bscore, score;
vector<pii> bsol, sol;
double initial_score;
vector<pii> initial_sol;
const int SAMPLES = 35;
const double PRUNE_THRESHOLD = 0;
ll pruning_samples = 0, pruning_rejected = 0;
const int di[4] = {-1, 1, 0, 0};
const int dj[4] = {0, 0, -1, 1};
bool cut[N*N];
unsigned char dry[SAMPLES][N*N];
unsigned long long dry_rows[SAMPLES][N];
int adj[N*N][4], deg[N*N], uncut_pos[N*N];
vector<pii> trees, uncut;
vector<int> uncut_bucket[10];
int bucket_pos[N*N], uncut_weight;
// Exact component cache for the committed cut set, separately for every sample.
int comp_id[SAMPLES][N*N], comp_size[SAMPLES][N*N];
int comp_head[SAMPLES][N*N], comp_tail[SAMPLES][N*N];
int comp_next[SAMPLES][N*N], comp_prev[SAMPLES][N*N];
vector<int> free_comp[SAMPLES];
ll cached_loss, proposed_loss;
int split_mode[SAMPLES], split_count[SAMPLES];
int split_nodes[SAMPLES][N*N], split_part[SAMPLES][N*N];
int split_end[SAMPLES][4], split_size[SAMPLES][4];
unsigned int visit_stamp, visited[N*N], target[N*N];
const int LOGN = 1 << 16;
double logs[LOGN];
template<class T> T sqr(T x) { return x*x; }
void AddToBucket(int v) {
int w = d[v/n][v%n];
bucket_pos[v] = SZ(uncut_bucket[w]);
uncut_bucket[w].push_back(v);
uncut_weight += w*w;
}
void RemoveFromBucket(int v) {
int w = d[v/n][v%n], p = bucket_pos[v];
int last = uncut_bucket[w].back();
uncut_bucket[w][p] = last;
bucket_pos[last] = p;
uncut_bucket[w].pop_back();
bucket_pos[v] = -1;
uncut_weight -= w*w;
}
int RandomUncut() {
int ticket = my.nextInt(uncut_weight), w = 1;
for (; w < 9; w++) {
int weight = w*w * SZ(uncut_bucket[w]);
if (ticket < weight) break;
ticket -= weight;
}
int v = uncut_bucket[w][my.nextInt(SZ(uncut_bucket[w]))];
return uncut_pos[v];
}
ll SampleLoss(const unsigned char* sample, const bool* cuts) {
ll total = 0;
unsigned char used[N*N];
int q[N*N];
F0(v, n*n) used[v] = cuts[v] || !sample[v];
F0(v, n*n) if (!used[v]) {
int head = 0, tail = 0;
used[v] = 1;
q[tail++] = v;
while (head < tail) {
int x = q[head++];
F0(t, deg[x]) {
int y = adj[x][t];
if (!used[y]) {
used[y] = 1;
q[tail++] = y;
}
}
}
total += 1LL * tail * tail;
}
return total;
}
ll RowSampleLoss(const unsigned long long* active) {
int parent[N*N], size[N*N];
auto root = [&](int v) {
while (parent[v] != v) {
parent[v] = parent[parent[v]];
v = parent[v];
}
return v;
};
ll total = 0;
unsigned long long prev = 0;
F0(i, n) {
unsigned long long remaining = active[i];
int base = i*n;
// Initialize each horizontal run as a component, then join vertical overlaps.
while (remaining) {
int j = __builtin_ctzll(remaining);
int len = __builtin_ctzll(~(remaining >> j));
int r = base+j;
F0(t, len) parent[r+t] = r;
size[r] = len;
total += len*len;
remaining &= ~(((1ULL << len)-1) << j);
}
unsigned long long both = prev & active[i];
unsigned long long starts = both & ~(both << 1);
while (starts) {
int j = __builtin_ctzll(starts);
starts &= starts-1;
int a = root(base-n+j), b = root(base+j);
if (a == b) continue;
if (size[a] < size[b]) swap(a, b);
total += 2LL*size[a]*size[b];
parent[b] = a;
size[a] += size[b];
}
prev = active[i];
}
return total;
}
double Evaluate() {
unsigned long long cut_rows[N] = {}, active[N];
F0(i, n) F0(j, n) cut_rows[i] |= (unsigned long long)cut[i*n+j] << j;
ll total = 0;
F0(s, SAMPLES) {
F0(i, n) active[i] = dry_rows[s][i] & ~cut_rows[i];
total += RowSampleLoss(active);
}
return total / (1.0 * SAMPLES * n * n);
}
void InitComponents() {
cached_loss = 0;
CL(-1, comp_id);
CL(0, comp_size);
CL(-1, comp_head);
CL(-1, comp_tail);
CL(-1, comp_next);
CL(-1, comp_prev);
CL(0, visited);
CL(0, target);
visit_stamp = 0;
int q[N*N];
F0(s, SAMPLES) {
free_comp[s].clear();
int count = 0;
F0(v, n*n) if (dry[s][v] && !cut[v] && comp_id[s][v] < 0) {
int id = count++, head = 0, tail = 0;
q[tail++] = v;
comp_id[s][v] = id;
while (head < tail) {
int x = q[head++];
F0(t, deg[x]) {
int y = adj[x][t];
if (dry[s][y] && !cut[y] && comp_id[s][y] < 0) {
comp_id[s][y] = id;
q[tail++] = y;
}
}
}
comp_head[s][id] = q[0];
comp_tail[s][id] = q[tail-1];
comp_size[s][id] = tail;
F0(t, tail) {
comp_prev[s][q[t]] = t ? q[t-1] : -1;
comp_next[s][q[t]] = t+1 < tail ? q[t+1] : -1;
}
cached_loss += 1LL*tail*tail;
}
for (int id = n*n-1; id >= count; id--) free_comp[s].push_back(id);
}
}
double EvaluateSwap(int a, int b, double allowed_delta) {
proposed_loss = cached_loss;
int start_sample = my.nextInt(SAMPLES);
F0(i, SAMPLES) {
int s = (start_sample+i) % SAMPLES;
split_mode[s] = 0;
split_count[s] = 0;
int removed = comp_id[s][b];
ll delta = 0;
if (removed >= 0) {
split_mode[s] = 1; // Removal leaves one component (possibly empty).
int old_size = comp_size[s][removed];
delta = 1-2LL*old_size;
int nb[4], nn = 0;
F0(t, deg[b]) {
int v = adj[b][t];
if (comp_id[s][v] == removed) nb[nn++] = v;
}
if (nn > 1) {
if (++visit_stamp == 0) {
CL(0, visited);
CL(0, target);
visit_stamp = 1;
}
unsigned int stamp = visit_stamp;
F0(t, nn) target[nb[t]] = stamp;
int* q = split_nodes[s];
int head = 0, tail = 1, remaining = nn-1;
q[0] = nb[0];
visited[nb[0]] = stamp;
split_part[s][nb[0]] = 0;
// Once all neighbors of b are connected without b, no split is possible.
while (head < tail && remaining) {
int v = q[head++];
F0(t, deg[v]) {
int u = adj[v][t];
if (u == b || comp_id[s][u] != removed || visited[u] == stamp) continue;
visited[u] = stamp;
split_part[s][u] = 0;
q[tail++] = u;
if (target[u] == stamp) remaining--;
}
}
if (remaining) {
// The first fragment was exhausted; enumerate the remaining fragments.
split_mode[s] = 2;
split_count[s] = 1;
split_end[s][0] = tail;
split_size[s][0] = tail;
F0(t, nn) if (visited[nb[t]] != stamp) {
int part = split_count[s]++, start = tail;
q[tail++] = nb[t];
visited[nb[t]] = stamp;
split_part[s][nb[t]] = part;
head = start;
while (head < tail) {
int v = q[head++];
F0(z, deg[v]) {
int u = adj[v][z];
if (u == b || comp_id[s][u] != removed || visited[u] == stamp) continue;
visited[u] = stamp;
split_part[s][u] = part;
q[tail++] = u;
}
}
split_end[s][part] = tail;
split_size[s][part] = tail-start;
}
delta = -1LL*old_size*old_size;
F0(t, split_count[s]) delta += 1LL*split_size[s][t]*split_size[s][t];
}
}
}
if (dry[s][a]) {
int groups[4], ng = 0;
ll merged = 1, separate = 0;
F0(t, deg[a]) {
int v = adj[a][t], id = comp_id[s][v];
if (v == b || id < 0) continue;
int key = id, size = comp_size[s][id];
if (id == removed) {
if (split_mode[s] == 2) {
int part = split_part[s][v];
key = n*n+part;
size = split_size[s][part];
} else size--;
}
bool seen = false;
F0(j, ng) if (groups[j] == key) seen = true;
if (seen) continue;
groups[ng++] = key;
merged += size;
separate += 1LL*size*size;
}
delta += merged*merged-separate;
}
proposed_loss += delta;
pruning_samples++;
// Keep the full evaluation divisor for the samples processed so far.
double partial_delta = (proposed_loss-cached_loss) / (1.0*SAMPLES*n*n);
if (partial_delta > allowed_delta + PRUNE_THRESHOLD) {
pruning_rejected++;
return HUGE_VAL;
}
}
return proposed_loss / (1.0*SAMPLES*n*n);
}
void MergeComponents(int s, int a, int b) {
if (a == b) return;
if (comp_size[s][a] < comp_size[s][b]) swap(a, b);
for (int v = comp_head[s][b]; v >= 0; v = comp_next[s][v]) comp_id[s][v] = a;
comp_next[s][comp_tail[s][a]] = comp_head[s][b];
comp_prev[s][comp_head[s][b]] = comp_tail[s][a];
comp_tail[s][a] = comp_tail[s][b];
comp_size[s][a] += comp_size[s][b];
comp_head[s][b] = comp_tail[s][b] = -1;
comp_size[s][b] = 0;
free_comp[s].push_back(b);
}
void AcceptSwap(int a, int b) {
F0(s, SAMPLES) {
int removed = comp_id[s][b];
if (removed >= 0) {
if (split_mode[s] == 2) {
int start = 0;
F0(part, split_count[s]) {
int id = removed;
if (part) { id = free_comp[s].back(); free_comp[s].pop_back(); }
int end = split_end[s][part];
comp_head[s][id] = split_nodes[s][start];
comp_tail[s][id] = split_nodes[s][end-1];
comp_size[s][id] = end-start;
for (int p = start; p < end; p++) {
int v = split_nodes[s][p];
comp_id[s][v] = id;
comp_prev[s][v] = p > start ? split_nodes[s][p-1] : -1;
comp_next[s][v] = p+1 < end ? split_nodes[s][p+1] : -1;
}
start = end;
}
} else {
int prev = comp_prev[s][b], next = comp_next[s][b];
if (prev >= 0) comp_next[s][prev] = next;
else comp_head[s][removed] = next;
if (next >= 0) comp_prev[s][next] = prev;
else comp_tail[s][removed] = prev;
if (--comp_size[s][removed] == 0) free_comp[s].push_back(removed);
}
comp_id[s][b] = comp_next[s][b] = comp_prev[s][b] = -1;
}
if (dry[s][a]) {
int id = free_comp[s].back(); free_comp[s].pop_back();
comp_id[s][a] = id;
comp_head[s][id] = comp_tail[s][id] = a;
comp_size[s][id] = 1;
comp_prev[s][a] = comp_next[s][a] = -1;
F0(t, deg[a]) {
int v = adj[a][t];
if (comp_id[s][v] >= 0) MergeComponents(s, comp_id[s][a], comp_id[s][v]);
}
}
}
cached_loss = proposed_loss;
}
void TraceScores() {
const int ACTUAL_SAMPLES = 40000;
bool initial_cut[N*N] = {}, final_cut[N*N] = {};
for (pii p : initial_sol) initial_cut[p.first*n+p.second] = true;
for (pii p : bsol) final_cut[p.first*n+p.second] = true;
// Match sample_seed(), splitmix64(), and fill_dry() in the official tools.
using ull = unsigned long long;
ull state = 1469598103934665603ULL;
ull threshold[N*N+1] = {};
F0(i, n) F0(j, n) {
state ^= '0' + d[i][j];
state *= 1099511628211ULL;
threshold[i*n+j] = (ull)(d[i][j] * (4294967296.0 / 10.0));
}
state ^= (ull)n * 1000003ULL + (ull)k * 998244353ULL;
auto next64 = [&]() {
state += 0x9E3779B97F4A7C15ULL;
ull z = state;
z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
return z ^ (z >> 31);
};
unsigned char sample[N*N+1];
ll initial_total = 0, final_total = 0;
F0(s, ACTUAL_SAMPLES) {
for (int v = 0; v < n*n; v += 2) {
ull bits = next64();
sample[v] = (bits & 0xFFFFFFFFULL) < threshold[v];
sample[v+1] = (bits >> 32) < threshold[v+1];
}
initial_total += SampleLoss(sample, initial_cut);
final_total += SampleLoss(sample, final_cut);
}
ios::fmtflags flags = cerr.flags();
streamsize prec = cerr.precision();
cerr.setf(ios::fixed, ios::floatfield);
cerr.precision(6);
cerr << "Initial grid score (" << SAMPLES << " samples): " << initial_score << '\n';
cerr << "Actual initial grid score (40000 samples): "
<< initial_total / (1.0 * ACTUAL_SAMPLES * n * n) << '\n';
cerr << "Final grid score (" << SAMPLES << " samples): " << bscore << '\n';
cerr << "Actual final grid score (40000 samples): "
<< final_total / (1.0 * ACTUAL_SAMPLES * n * n) << '\n';
cerr.flags(flags);
cerr.precision(prec);
}
void Prepare() {
PR(n, k);
sol.clear();
bsol.clear();
trees.clear();
uncut.clear();
F0(w, 10) uncut_bucket[w].clear();
uncut_weight = 0;
CL(-1, bucket_pos);
CL(0, cut);
CL(0, deg);
CL(-1, uncut_pos);
F0(i, n) F0(j, n) {
int v = i*n+j;
if (d[i][j]) trees.push_back({i, j});
F0(t, 4) {
int ni = i+di[t], nj = j+dj[t];
if (ni >= 0 && ni < n && nj >= 0 && nj < n)
adj[v][deg[v]++] = ni*n+nj;
}
}
CL(0, dry_rows);
F0(s, SAMPLES) F0(i, n) F0(j, n) {
dry[s][i*n+j] = my.nextInt(10) < d[i][j];
dry_rows[s][i] |= (unsigned long long)dry[s][i*n+j] << j;
}
bscore = inf;
F0(i, LOGN) logs[i] = -log((i+0.5)/LOGN);
}
void UpdateBest() {
if (score < bscore) {
bscore = score;
bsol = sol;
}
}
int sa_consider[64], sa_accept[64], sa_regress[64], sa_total[64];
void Improve() {
Rand sa_rng(1);
vector<double> sa_type_prob = {0.4, 0.2, 0.6};
int tn = 3;
const int diag_i[4] = {-1, -1, 1, 1};
const int diag_j[4] = {-1, 1, -1, 1};
sa_rng.PrepareWeightedSample(sa_type_prob);
F0(t, tn) {
sa_consider[t] = sa_accept[t] = sa_regress[t] = sa_total[t] = 0;
t_o[t] = 0;
}
int tot = 1, acc = 0;
double T2 = 0.30, T1 = 0.00, TEMP = 0.0, r = 0.0;
double startTime = Elapsed();
double endTime = TL;
if (sol.empty() || uncut.empty() || startTime >= endTime) return;
for (int iter = 0; ; iter++) {
double now = Elapsed();
if (now >= endTime) { PR(iter); break; }
r = (endTime - now) / (endTime - startTime);
TEMP = T1 + (T2 - T1) * r;
int tp = sa_rng.WeightedSample();
AT(tp);
sa_consider[tp]++;
int p = my.nextInt(SZ(sol)), u;
pii old = sol[p], next;
if (tp == 0) {
u = RandomUncut();
next = uncut[u];
} else {
int t = my.nextInt(4);
if (tp == 1) next = {old.first+di[t], old.second+dj[t]};
else {
if (SZ(sol) < 2) continue;
// Keep the anchor and restore a different picked tree.
int anchor = p;
next = {sol[anchor].first+diag_i[t], sol[anchor].second+diag_j[t]};
p = my.nextInt(SZ(sol)-1);
if (p >= anchor) p++;
old = sol[p];
}
if (next.first < 0 || next.first >= n || next.second < 0 || next.second >= n) continue;
u = uncut_pos[next.first*n+next.second];
if (u < 0) continue;
}
int a = old.first*n+old.second, b = next.first*n+next.second;
cut[a] = false;
cut[b] = true;
double allowed_delta = TEMP * logs[my.nextInt(LOGN)];
double next_score = EvaluateSwap(a, b, allowed_delta);
double delta = next_score - score;
sa_total[tp]++;
if (delta > 0) tot++;
if (delta <= 0 || delta <= allowed_delta) {
AcceptSwap(a, b);
sa_accept[tp]++;
if (delta > 0) { acc++; sa_regress[tp]++; }
sol[p] = next;
uncut[u] = old;
uncut_pos[a] = u;
uncut_pos[b] = -1;
RemoveFromBucket(b);
AddToBucket(a);
score = next_score;
UpdateBest();
} else {
cut[a] = true;
cut[b] = false;
}
}
if (1) {
cerr << acc << "/" << tot << " "
<< 100.0 * acc / tot << " "
<< score << "/" << bscore << endl;
}
auto sa_rate = [](int num, int den) -> double {
return den ? 100.0 * num / den : 0.0;
};
ios::fmtflags sa_flags = cerr.flags();
streamsize sa_prec = cerr.precision();
cerr.setf(ios::fixed, ios::floatfield);
cerr.precision(1);
cerr << "type ms consider accept regress total acc% reg%\n";
F0(ti, tn) {
cerr.width(4); cerr << ti;
cerr << " ";
cerr.width(9); cerr << 1000.0 * t_o[ti];
cerr << " ";
cerr.width(8); cerr << sa_consider[ti];
cerr << " ";
cerr.width(8); cerr << sa_accept[ti];
cerr << " ";
cerr.width(8); cerr << sa_regress[ti];
cerr << " ";
cerr.width(8); cerr << sa_total[ti];
cerr << " ";
cerr.width(7); cerr << sa_rate(sa_accept[ti], sa_total[ti]);
cerr << " ";
cerr.width(7); cerr << sa_rate(sa_regress[ti], sa_total[ti]);
cerr << '\n';
}
cerr << "Pruned transitions: " << pruning_rejected << '\n';
cerr << "Samples evaluated: " << pruning_samples << '\n';
cerr.flags(sa_flags);
cerr.precision(sa_prec);
}
void SaSolution() {
// Scale (d + 0.2 * sum(neighbor d)) by 10 for exact comparisons.
F0(i, n) F0(j, n) {
int v = i*n+j;
W[i][j] = 10*d[i][j];
F0(a, deg[v]) {
int u = adj[v][a];
W[i][j] += 2*d[u/n][u%n];
}
}
F0(iter, k) {
int best = -1, best_weight = 0;
F0(t, SZ(trees)) {
pii p = trees[t];
int v = p.first*n+p.second;
if (cut[v] || W[p.first][p.second] <= best_weight) continue;
bool allowed = true;
F0(a, deg[v]) if (cut[adj[v][a]]) allowed = false;
if (allowed) {
best = t;
best_weight = W[p.first][p.second];
}
}
if (best < 0) break;
pii p = trees[best];
sol.push_back(p);
cut[p.first*n+p.second] = true;
}
F0(t, SZ(trees)) {
pii p = trees[t];
int v = p.first*n+p.second;
if (cut[v]) continue;
uncut_pos[v] = SZ(uncut);
uncut.push_back(p);
AddToBucket(v);
}
InitComponents();
score = Evaluate();
initial_score = score;
initial_sol = sol;
UpdateBest();
Improve();
}
void Solve() {
saveTime = GetSeconds();
Prepare();
SaSolution();
cout << SZ(bsol) << endl;
F0(i, SZ(bsol)) {
cout << bsol[i].first << " " << bsol[i].second << endl;
}
#ifdef LOCAL
TraceScores();
#endif
//Report();
}
void ReadInput() {
cin >> n >> k;
F0(i, n) {
string row;
cin >> row;
F0(j, n) d[i][j] = row[j] - '0';
}
}
int main(int argc, char* argv[]) {
Init();
int seed1 = 0, seed2 = 0;
if (argc>1) {
if (argc == 2) {
seed1 = seed2 = atoi(argv[1]);
} else {
seed1 = atoi(argv[1]);
seed2 = atoi(argv[2]);
}
STANDARD=0;
}
if (STANDARD) {
ReadInput();
Solve();
return 0;
}
for (int seed=seed1; seed<=seed2; seed++) {
if (seed>=0 && seed<10000) {
char inp[128];
sprintf(inp, "in/%04d.txt", seed);
char outp[128];
sprintf(outp, "out/%04d.txt", seed);
ignore = freopen(inp, "r", stdin);
ignore = freopen(outp, "w", stdout);
ReadInput();
Solve();
cerr << "Seed #" << seed << " ";
cerr << bscore << endl;
//cout << "Score would be " << bscore << endl;
} else {
// Generate
throw;
Rand my(seed);
}
}
return 0;
}