Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup / docker_space /frontier_cs_6 /examples /gpt5_high_1.cpp
JustinTX's picture
JustinTX
Add files using upload-large-folder tool
1fd0050 verified
Raw History Blame Contribute Delete
18.9 kB
#include <bits/stdc++.h>
using namespace std;
static const int KMAX = 240;
struct RNG {
uint64_t seed;
RNG(uint64_t s=123456789) : seed(s) {}
inline uint64_t next() {
seed ^= seed << 7;
seed ^= seed >> 9;
return seed;
}
inline int randint(int n) { // [0, n)
return (int)(next() % (uint64_t)n);
}
inline bool coin() { return (next() >> 63) & 1; }
};
struct WorldMapBuilder {
int N, M;
vector<int> A, B;
vector<vector<char>> adj; // adj[u][v] true if edge exists between u and v
vector<vector<char>> allow; // allow[u][v] true if u==v or adj[u][v]
int K; // grid size
vector<vector<int>> grid;
RNG rng;
WorldMapBuilder(int n, int m, const vector<int>& a, const vector<int>& b, uint64_t seed)
: N(n), M(m), A(a), B(b), adj(n, vector<char>(n, 0)), allow(n, vector<char>(n, 0)), rng(seed) {
for (int i = 0; i < M; ++i) {
int u = A[i]-1;
int v = B[i]-1;
adj[u][v] = adj[v][u] = 1;
}
for (int i = 0; i < N; ++i) {
allow[i][i] = 1;
for (int j = 0; j < N; ++j) if (adj[i][j]) allow[i][j] = 1;
}
// Choose K: try to keep moderate but enough to cover edges
K = min(KMAX, max(2*N, 100));
grid.assign(K, vector<int>(K, 0));
}
vector<int> dfs_walk() {
vector<vector<int>> G(N);
for (int u = 0; u < N; ++u) for (int v = 0; v < N; ++v) if (adj[u][v]) G[u].push_back(v);
// Shuffle neighbors to add randomness
for (int u = 0; u < N; ++u) {
for (int i = (int)G[u].size()-1; i > 0; --i) {
int j = rng.randint(i+1);
swap(G[u][i], G[u][j]);
}
}
vector<int> walk;
vector<char> vis(N, 0);
int root = 0;
// In case of isolated single node graph (N==1 allowed)
function<void(int,int)> dfs = [&](int u, int p){
vis[u] = 1;
walk.push_back(u);
for (int v : G[u]) {
if (!vis[v]) {
dfs(v, u);
walk.push_back(u);
}
}
};
dfs(root, -1);
if (walk.empty()) walk.push_back(0);
// Ensure it ends at root
if (walk.back() != root) walk.push_back(root);
return walk;
}
inline void markEdge(int u, int v, vector<vector<char>>& covered) {
if (u == v) return;
if (!adj[u][v]) return;
int x = min(u, v), y = max(u, v);
covered[x][y] = 1;
}
void collectCovered(const vector<vector<int>>& g, vector<vector<char>>& covered) {
for (int i = 0; i < N; ++i) for (int j = i+1; j < N; ++j) covered[i][j] = 0;
for (int r = 0; r < K; ++r) {
for (int c = 1; c < K; ++c) markEdge(g[r][c-1], g[r][c], covered);
}
for (int r = 1; r < K; ++r) {
for (int c = 0; c < K; ++c) markEdge(g[r-1][c], g[r][c], covered);
}
}
vector<int> build_first_row_from_walk(const vector<int>& walk) {
vector<int> row(K);
for (int c = 0; c < K; ++c) row[c] = walk[c % (int)walk.size()];
return row;
}
// DP to build a row with optional forcing of an edge (u,v) horizontally.
// top: pointer to top row (nullptr if building first row)
// covered: current covered edges (for weighting)
// returns empty vector if impossible (shouldn't happen often)
vector<int> compute_row_dp(const vector<int>* top, const vector<vector<char>>& covered, int force_u = -1, int force_v = -1) {
bool enforce = (force_u != -1 && force_v != -1);
// Precompute allowed colors per column based on top constraint
vector<vector<int>> allowedCols(K);
if (top) {
allowedCols.assign(K, {});
for (int c = 0; c < K; ++c) {
int t = (*top)[c];
for (int x = 0; x < N; ++x) if (allow[x][t]) allowedCols[c].push_back(x);
// random shuffle to add diversity
for (int i = (int)allowedCols[c].size()-1; i > 0; --i) {
int j = rng.randint(i+1);
swap(allowedCols[c][i], allowedCols[c][j]);
}
}
} else {
vector<int> all(N);
iota(all.begin(), all.end(), 0);
for (int c = 0; c < K; ++c) {
allowedCols[c] = all;
for (int i = N-1; i > 0; --i) {
int j = rng.randint(i+1);
swap(allowedCols[c][i], allowedCols[c][j]);
}
}
}
const int NEG = -1e9;
// dp[c][x][used] -> best score
vector<array<int,2>> dp_prev(N, {NEG, NEG}), dp_cur(N, {NEG, NEG});
vector<vector<array<int,2>>> prv(K, vector<array<int,2>>(N, array<int,2>{-1,-1}));
auto wantEdge = [&](int a, int b)->bool{
if (a==b) return false;
int x = min(a,b), y = max(a,b);
if (!adj[x][y]) return false;
return !covered[x][y];
};
auto trans_w = [&](int y, int x)->int{
if (y == x) return 0;
return wantEdge(y, x) ? 2 : 0; // horizontal edges weight 2
};
auto node_w = [&](int c, int x)->int{
if (!top) return 0;
int t = (*top)[c];
if (t == x) return 0;
return wantEdge(t, x) ? 1 : 0; // vertical edges weight 1
};
// Initialize column 0
for (int x : allowedCols[0]) {
int used = 0;
dp_prev[x][0] = node_w(0, x);
dp_prev[x][1] = NEG; // cannot have used forced edge at first cell
}
// Iterate columns
for (int c = 1; c < K; ++c) {
// reset dp_cur
for (int x = 0; x < N; ++x) dp_cur[x][0] = dp_cur[x][1] = NEG;
for (int x : allowedCols[c]) {
int nw = node_w(c, x);
for (int y : allowedCols[c-1]) {
if (!allow[y][x]) continue;
// used=0
if (dp_prev[y][0] > NEG/2) {
int inc = trans_w(y, x) + nw;
int used = 0;
if (enforce && ((y==force_u && x==force_v) || (y==force_v && x==force_u))) used = 1;
int cand = dp_prev[y][0] + inc;
if (cand > dp_cur[x][used] || (cand == dp_cur[x][used] && rng.coin())) {
dp_cur[x][used] = cand;
prv[c][x][used] = y;
}
}
// used=1
if (dp_prev[y][1] > NEG/2) {
int inc = trans_w(y, x) + nw;
int used = 1;
int cand = dp_prev[y][1] + inc;
if (cand > dp_cur[x][used] || (cand == dp_cur[x][used] && rng.coin())) {
dp_cur[x][used] = cand;
prv[c][x][used] = y;
}
}
}
}
// swap
for (int x = 0; x < N; ++x) {
dp_prev[x][0] = dp_cur[x][0];
dp_prev[x][1] = dp_cur[x][1];
dp_cur[x][0] = dp_cur[x][1] = NEG;
}
}
// Choose best ending
int best_used = enforce ? 1 : 0;
int best_x = -1, best_val = NEG;
for (int x : allowedCols[K-1]) {
for (int u = (enforce?1:0); u <= 1; ++u) {
if (!enforce && u==0) {
if (dp_prev[x][u] > best_val || (dp_prev[x][u] == best_val && rng.coin())) {
best_val = dp_prev[x][u];
best_x = x;
best_used = u;
}
} else if (enforce && u==1) {
if (dp_prev[x][u] > best_val || (dp_prev[x][u] == best_val && rng.coin())) {
best_val = dp_prev[x][u];
best_x = x;
best_used = u;
}
} else if (!enforce && u==1) {
if (dp_prev[x][u] > best_val || (dp_prev[x][u] == best_val && rng.coin())) {
best_val = dp_prev[x][u];
best_x = x;
best_used = u;
}
}
}
}
if (best_x == -1) {
// Fallback: copy top row if exists, else random row following self loops
vector<int> fallback(K);
if (top) {
fallback = *top;
} else {
for (int c = 0; c < K; ++c) fallback[c] = rng.randint(N);
}
return fallback;
}
// Reconstruct
vector<int> row(K);
int x = best_x;
int used = best_used;
for (int c = K-1; c >= 0; --c) {
row[c] = x;
if (c == 0) break;
int y = prv[c][x][used];
if (enforce) {
// determine if the pair (y,x) matched the forced edge to backtrack used flag
if (used == 1) {
if ((y==force_u && x==force_v) || (y==force_v && x==force_u)) {
// previous used flag may have been 0
// but could also be 1 if multiple matches; we don't know; try both:
// We stored only one predecessor y; to know previous 'used' we can recompute:
// Check if dp_prev[y][1] led to dp[c][x][1] with equal score; If not, then used came from a new match -> previous was 0.
// For simplicity, we will attempt to deduce previous used state:
// We'll recompute quick conditions; but we didn't store scores; We'll approximate:
// To avoid complexity, we can mark used=0 when encountering the first matching pair in backtracking.
used = 0;
}
}
}
x = y;
}
return row;
}
void update_covered_with_row(int r, const vector<int>* top, const vector<int>& row, vector<vector<char>>& covered) {
// horizontal in row
for (int c = 1; c < K; ++c) markEdge(row[c-1], row[c], covered);
if (top) {
for (int c = 0; c < K; ++c) markEdge((*top)[c], row[c], covered);
}
}
bool all_edges_covered(const vector<vector<char>>& covered) {
for (int i = 0; i < M; ++i) {
int u = A[i]-1, v = B[i]-1;
int x = min(u, v), y = max(u, v);
if (!covered[x][y]) return false;
}
return true;
}
vector<pair<int,int>> missing_edges(const vector<vector<char>>& covered) {
vector<pair<int,int>> miss;
for (int i = 0; i < M; ++i) {
int u = A[i]-1, v = B[i]-1;
int x = min(u, v), y = max(u, v);
if (!covered[x][y]) miss.emplace_back(x, y);
}
return miss;
}
vector<vector<int>> build_once() {
vector<vector<int>> g(K, vector<int>(K, 0));
vector<vector<char>> covered(N, vector<char>(N, 0));
// row 0
vector<int> walk = dfs_walk();
vector<int> row0 = build_first_row_from_walk(walk);
g[0] = row0;
// update covered with row0 horizontally
update_covered_with_row(0, nullptr, row0, covered);
// build subsequent rows
for (int r = 1; r < K; ++r) {
vector<int> rowr = compute_row_dp(&g[r-1], covered, -1, -1);
g[r] = rowr;
update_covered_with_row(r, &g[r-1], rowr, covered);
}
// Ensure all colors appear at least once: if not, try to adjust slightly by random re-generation of some rows
vector<int> freq(N, 0);
for (int r = 0; r < K; ++r) for (int c = 0; c < K; ++c) freq[g[r][c]]++;
for (int col = 0; col < N; ++col) {
if (freq[col] == 0) {
// Try to force appearance by rebuilding a random row with no force edge (weights tend to include new colors)
int r = rng.randint(K);
vector<int> rowr = compute_row_dp((r>0 ? &g[r-1] : nullptr), covered, -1, -1);
g[r] = rowr;
// Rebuild all rows below to maintain vertical adjacency
// Recompute covered up to r
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) covered[i][j] = 0;
update_covered_with_row(0, nullptr, g[0], covered);
for (int i = 1; i <= r; ++i) update_covered_with_row(i, &g[i-1], g[i], covered);
for (int i = r+1; i < K; ++i) {
vector<int> rowi = compute_row_dp(&g[i-1], covered, -1, -1);
g[i] = rowi;
update_covered_with_row(i, &g[i-1], g[i], covered);
}
// update freq
freq.assign(N, 0);
for (int rr = 0; rr < K; ++rr) for (int c = 0; c < K; ++c) freq[g[rr][c]]++;
}
}
return g;
}
vector<vector<int>> repair_missing(vector<vector<int>>& g) {
// Attempt to repair missing edges by forcing rows
vector<vector<char>> covered(N, vector<char>(N, 0));
collectCovered(g, covered);
auto miss = missing_edges(covered);
if (miss.empty()) return g;
// Try to cover missing edges one by one
// Shuffle missing edges to randomize
for (int i = (int)miss.size()-1; i > 0; --i) {
int j = rng.randint(i+1);
swap(miss[i], miss[j]);
}
for (auto edge : miss) {
int fu = edge.first, fv = edge.second; // 0-based sorted
bool added = false;
// Try multiple rows randomly
vector<int> rows(K);
iota(rows.begin(), rows.end(), 0);
for (int i = K-1; i > 0; --i) {
int j = rng.randint(i+1);
swap(rows[i], rows[j]);
}
for (int rindex = 0; rindex < K && !added; ++rindex) {
int r = rows[rindex];
vector<vector<char>> covUp = covered; // copy baseline
// Recompute covered up to row r-1 to be safe
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) covUp[i][j] = 0;
update_covered_with_row(0, nullptr, g[0], covUp);
for (int i = 1; i < r; ++i) update_covered_with_row(i, &g[i-1], g[i], covUp);
vector<int>* top = (r > 0 ? &g[r-1] : nullptr);
vector<int> newRow = compute_row_dp(top, covUp, fu, fv);
if (newRow.empty()) continue;
// Apply and rebuild below rows
g[r] = newRow;
// Reset covered and rebuild from row r onwards to maximize adding missing edges
vector<vector<char>> cov(N, vector<char>(N, 0));
update_covered_with_row(0, nullptr, g[0], cov);
for (int i = 1; i <= r; ++i) update_covered_with_row(i, &g[i-1], g[i], cov);
for (int i = r+1; i < K; ++i) {
vector<int> ri = compute_row_dp(&g[i-1], cov, -1, -1);
g[i] = ri;
update_covered_with_row(i, &g[i-1], g[i], cov);
}
// Check if edge added
vector<vector<char>> covCheck(N, vector<char>(N, 0));
collectCovered(g, covCheck);
if (covCheck[fu][fv]) {
covered = covCheck;
added = true;
}
}
if (!added) {
// Failed to add this edge in current configuration, give up and return as is
return g;
}
}
return g;
}
vector<vector<int>> build_map() {
// Multiple attempts with randomization to ensure full coverage
for (int attempt = 0; attempt < 8; ++attempt) {
auto g = build_once();
vector<vector<char>> covered(N, vector<char>(N, 0));
collectCovered(g, covered);
if (all_edges_covered(covered)) {
grid = g;
return format_output();
}
auto g2 = repair_missing(g);
collectCovered(g2, covered);
if (all_edges_covered(covered)) {
grid = g2;
return format_output();
}
// Try again with different K maybe: increase K slightly if possible
if (K < KMAX) {
K = min(KMAX, K + max(5, N/2));
grid.assign(K, vector<int>(K, 0));
}
// re-seed slightly
rng.next();
}
// Fallback: ensure valid (no invalid adjacencies). Build trivial map repeating a DFS walk row by row (no vertical differences).
K = min(KMAX, max(2*N, 100));
grid.assign(K, vector<int>(K, 0));
vector<int> walk = dfs_walk();
for (int r = 0; r < K; ++r) {
auto row0 = build_first_row_from_walk(walk);
for (int c = 0; c < K; ++c) grid[r][c] = row0[c];
}
return format_output();
}
vector<vector<int>> format_output() {
vector<vector<int>> C(K, vector<int>(K, 0));
for (int r = 0; r < K; ++r) for (int c = 0; c < K; ++c) C[r][c] = grid[r][c] + 1;
return C;
}
};
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
// Seed RNG with hash of inputs for reproducibility
uint64_t seed = 1469598103934665603ull;
seed ^= (uint64_t)N + 0x9e3779b97f4a7c15ull + (seed<<6) + (seed>>2);
seed ^= (uint64_t)M + 0x9e3779b97f4a7c15ull + (seed<<6) + (seed>>2);
for (int x : A) { seed ^= (uint64_t)x + 0x9e3779b97f4a7c15ull + (seed<<6) + (seed>>2); }
for (int x : B) { seed ^= (uint64_t)x + 0x9e3779b97f4a7c15ull + (seed<<6) + (seed>>2); }
WorldMapBuilder builder(N, M, A, B, seed);
return builder.build_map();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
for (int tc = 0; tc < T; ++tc) {
int N, M;
cin >> N >> M;
vector<int> A(M), B(M);
for (int i = 0; i < M; ++i) cin >> A[i] >> B[i];
auto C = create_map(N, M, A, B);
int P = (int)C.size();
cout << P << "\n";
for (int i = 0; i < P; ++i) {
cout << (int)C[i].size() << (i+1==P?'\n':' ');
}
cout << "\n";
for (int i = 0; i < P; ++i) {
for (int j = 0; j < (int)C[i].size(); ++j) {
if (j) cout << ' ';
cout << C[i][j];
}
cout << "\n";
}
cout.flush();
}
return 0;
}