oj.uz

Submission #1099917

# Submission time Handle Problem Language Result Execution time Memory
1099917 2024-10-12T05:51:12 Z model_code Sphinx's Riddle (IOI24_sphinx) C++17
64 / 100
 407 ms 932 KB 
// failed/GA_heuristic.cpp

#include <algorithm>
#include <random>

#include "sphinx.h"

using namespace std;

const int MIN_DEG = 40;

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(1234567);
  ::N = N;
  edges.resize(N, vector<bool>(N));
  possible_colors.resize(N, vector<bool>(N, true));
  deg.resize(N);
  int M = X.size();
  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;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 8

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB #experiments: 2
2 Correct 0 ms 344 KB #experiments: 3
3 Correct 0 ms 380 KB #experiments: 3
4 Correct 0 ms 344 KB #experiments: 4

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 8
2 Correct 1 ms 344 KB #experiments: 2
3 Correct 0 ms 344 KB #experiments: 3
4 Correct 0 ms 380 KB #experiments: 3
5 Correct 0 ms 344 KB #experiments: 4
6 Correct 3 ms 340 KB #experiments: 250
7 Correct 3 ms 344 KB #experiments: 298
8 Correct 7 ms 344 KB #experiments: 294
9 Correct 4 ms 344 KB #experiments: 292
10 Correct 4 ms 600 KB #experiments: 304
11 Correct 6 ms 344 KB #experiments: 292
12 Correct 6 ms 344 KB #experiments: 289
13 Correct 4 ms 344 KB #experiments: 305
14 Correct 4 ms 344 KB #experiments: 286
15 Correct 4 ms 344 KB #experiments: 287
16 Correct 4 ms 344 KB #experiments: 290
17 Correct 5 ms 344 KB #experiments: 283
18 Correct 6 ms 344 KB #experiments: 287
19 Correct 4 ms 344 KB #experiments: 275
20 Correct 4 ms 344 KB #experiments: 285
21 Correct 4 ms 344 KB #experiments: 286
22 Correct 5 ms 344 KB #experiments: 237
23 Correct 5 ms 436 KB #experiments: 241
24 Correct 5 ms 344 KB #experiments: 225
25 Correct 6 ms 344 KB #experiments: 316
26 Correct 5 ms 352 KB #experiments: 292
27 Correct 4 ms 344 KB #experiments: 303
28 Correct 4 ms 436 KB #experiments: 317
29 Correct 7 ms 344 KB #experiments: 350
30 Correct 8 ms 344 KB #experiments: 406
31 Correct 10 ms 352 KB #experiments: 503
32 Correct 7 ms 344 KB #experiments: 426
33 Correct 7 ms 344 KB #experiments: 268
34 Correct 10 ms 344 KB #experiments: 567

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB #experiments: 2
2 Correct 0 ms 344 KB #experiments: 3
3 Correct 0 ms 380 KB #experiments: 3
4 Correct 0 ms 344 KB #experiments: 4
5 Correct 3 ms 340 KB #experiments: 250
6 Correct 3 ms 344 KB #experiments: 298
7 Correct 7 ms 344 KB #experiments: 294
8 Correct 4 ms 344 KB #experiments: 292
9 Correct 4 ms 600 KB #experiments: 304
10 Correct 6 ms 344 KB #experiments: 292
11 Correct 6 ms 344 KB #experiments: 289
12 Correct 4 ms 344 KB #experiments: 305
13 Correct 198 ms 484 KB #experiments: 2028
14 Correct 250 ms 484 KB #experiments: 2113
15 Correct 255 ms 728 KB #experiments: 2029
16 Correct 271 ms 728 KB #experiments: 2082
17 Correct 257 ms 732 KB #experiments: 2081
18 Correct 231 ms 728 KB #experiments: 2112
19 Correct 234 ms 600 KB #experiments: 2102
20 Correct 209 ms 484 KB #experiments: 1800
21 Correct 296 ms 484 KB #experiments: 2141

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB #experiments: 2
2 Correct 0 ms 344 KB #experiments: 3
3 Correct 0 ms 380 KB #experiments: 3
4 Correct 0 ms 344 KB #experiments: 4
5 Correct 4 ms 344 KB #experiments: 286
6 Correct 4 ms 344 KB #experiments: 287
7 Correct 4 ms 344 KB #experiments: 290
8 Correct 5 ms 344 KB #experiments: 283
9 Correct 6 ms 344 KB #experiments: 287
10 Correct 4 ms 344 KB #experiments: 275
11 Correct 4 ms 344 KB #experiments: 285
12 Correct 4 ms 344 KB #experiments: 286
13 Correct 325 ms 856 KB #experiments: 1993
14 Correct 309 ms 856 KB #experiments: 1995
15 Correct 288 ms 932 KB #experiments: 1991
16 Correct 328 ms 856 KB #experiments: 1997
17 Correct 327 ms 856 KB #experiments: 1993
18 Correct 317 ms 920 KB #experiments: 1998
19 Correct 282 ms 856 KB #experiments: 1996
20 Correct 300 ms 856 KB #experiments: 1990
21 Correct 327 ms 856 KB #experiments: 1998

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 8
2 Correct 1 ms 344 KB #experiments: 2
3 Correct 0 ms 344 KB #experiments: 3
4 Correct 0 ms 380 KB #experiments: 3
5 Correct 0 ms 344 KB #experiments: 4
6 Correct 3 ms 340 KB #experiments: 250
7 Correct 3 ms 344 KB #experiments: 298
8 Correct 7 ms 344 KB #experiments: 294
9 Correct 4 ms 344 KB #experiments: 292
10 Correct 4 ms 600 KB #experiments: 304
11 Correct 6 ms 344 KB #experiments: 292
12 Correct 6 ms 344 KB #experiments: 289
13 Correct 4 ms 344 KB #experiments: 305
14 Correct 4 ms 344 KB #experiments: 286
15 Correct 4 ms 344 KB #experiments: 287
16 Correct 4 ms 344 KB #experiments: 290
17 Correct 5 ms 344 KB #experiments: 283
18 Correct 6 ms 344 KB #experiments: 287
19 Correct 4 ms 344 KB #experiments: 275
20 Correct 4 ms 344 KB #experiments: 285
21 Correct 4 ms 344 KB #experiments: 286
22 Correct 5 ms 344 KB #experiments: 237
23 Correct 5 ms 436 KB #experiments: 241
24 Correct 5 ms 344 KB #experiments: 225
25 Correct 6 ms 344 KB #experiments: 316
26 Correct 5 ms 352 KB #experiments: 292
27 Correct 4 ms 344 KB #experiments: 303
28 Correct 4 ms 436 KB #experiments: 317
29 Correct 7 ms 344 KB #experiments: 350
30 Correct 8 ms 344 KB #experiments: 406
31 Correct 10 ms 352 KB #experiments: 503
32 Correct 7 ms 344 KB #experiments: 426
33 Correct 7 ms 344 KB #experiments: 268
34 Correct 10 ms 344 KB #experiments: 567
35 Correct 198 ms 484 KB #experiments: 2028
36 Correct 250 ms 484 KB #experiments: 2113
37 Correct 255 ms 728 KB #experiments: 2029
38 Correct 271 ms 728 KB #experiments: 2082
39 Correct 257 ms 732 KB #experiments: 2081
40 Correct 231 ms 728 KB #experiments: 2112
41 Correct 234 ms 600 KB #experiments: 2102
42 Correct 209 ms 484 KB #experiments: 1800
43 Correct 296 ms 484 KB #experiments: 2141
44 Correct 325 ms 856 KB #experiments: 1993
45 Correct 309 ms 856 KB #experiments: 1995
46 Correct 288 ms 932 KB #experiments: 1991
47 Correct 328 ms 856 KB #experiments: 1997
48 Correct 327 ms 856 KB #experiments: 1993
49 Correct 317 ms 920 KB #experiments: 1998
50 Correct 282 ms 856 KB #experiments: 1996
51 Correct 300 ms 856 KB #experiments: 1990
52 Correct 327 ms 856 KB #experiments: 1998
53 Incorrect 407 ms 752 KB #experiments reached 2751
54 Halted 0 ms 0 KB -