Submission #1099918

#TimeUsernameProblemLanguageResultExecution timeMemory
1099918model_codeSphinx's Riddle (IOI24_sphinx)C++17
64 / 100
374 ms924 KiB
// failed/GA_heuristic_painful.cpp #include <algorithm> #include <chrono> #include <random> #include "sphinx.h" using namespace std; const int MIN_DEG = 25; int N; vector<vector<bool>> edges; vector<int> deg; default_random_engine r; vector<vector<bool>> possible_colors; int count_components(const vector<int> &coloring) { int res = 0; vector<int> done(N); for (int i = 0; i < N; i++) { if (done[i]) continue; res++; done[i] = true; vector<int> stack = {i}; while (stack.size()) { int j = stack.back(); stack.pop_back(); for (int k = 0; k < N; k++) { if (edges[j][k] && coloring[j] == coloring[k] && !done[k]) { done[k] = true; stack.push_back(k); } } } } return res; } int find_single(int i) { vector<int> colors(N); iota(colors.begin(), colors.end(), 0); shuffle(colors.begin(), colors.end(), r); int start = 0; int len = N; while (len > 1) { vector<int> v(N, N); v[i] = -1; int k = 0; for (int j = 0; j < N && k < len / 2; j++) { if (edges[i][j]) { v[j] = colors[start + k++]; } } if (perform_experiment(v) == count_components(v)) { start += k; len -= k; } else { len = k; } } return colors[start]; } vector<int> find_indep(vector<int> vertices) { vector<int> res0; shuffle(vertices.begin(), vertices.end(), r); vector<int> res; for (int i : vertices) { bool good = true; for (int j : res) { if (edges[i][j]) { good = false; } } if (good) { res.push_back(i); } } return res; } int find_in_indep(const vector<int> &indep, int i) { vector<int> v0(N, i); for (int j : indep) { v0[j] = -1; } if (perform_experiment(v0) == count_components(v0)) { for (int j : indep) { possible_colors[j][i] = false; } return -1; } int start = 0; int len = indep.size(); while (len > 1) { vector<int> v(N, i); int k = len / 2; for (int j = 0; j < k; j++) { v[indep[start + j]] = -1; } if (perform_experiment(v) == count_components(v)) { for (int j = start; j < start + k; j++) { possible_colors[indep[j]][i] = false; } start += k; len -= k; } else { len = k; } } return indep[start]; } std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) { r.seed(chrono::system_clock::now().time_since_epoch().count()); ::N = N; int M = X.size(); edges.resize(N, vector<bool>(N)); possible_colors.resize(N, vector<bool>(N, true)); deg.resize(N); for (int i = 0; i < M; i++) { edges[X[i]][Y[i]] = edges[Y[i]][X[i]] = true; deg[X[i]]++; deg[Y[i]]++; } vector<int> res(N, -1); for (int i = 0; i < N; i++) { if (deg[i] >= MIN_DEG) { res[i] = find_single(i); } } while (true) { vector<int> remaining; for (int i = 0; i < N; i++) { if (res[i] == -1) { remaining.push_back(i); } } if (!remaining.size()) { break; } vector<int> indep = find_indep(remaining); int best_color = -1; int best_count = 0; for (int i = 0; i < N; i++) { int count = 0; for (int j : indep) { if (possible_colors[j][i]) { count++; } } if (count > best_count) { best_count = count; best_color = i; } } vector<int> indep2; for (int j : indep) { if (possible_colors[j][best_color]) { indep2.push_back(j); } } int c = find_in_indep(indep2, best_color); if (c != -1) { res[c] = best_color; } } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...