oj.uz

Submission #1099918

# Submission time Handle Problem Language Result Execution time Memory
1099918 2024-10-12T05:51:25 Z model_code Sphinx's Riddle (IOI24_sphinx) C++17
64 / 100
 374 ms 924 KB 
// 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;
}

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 0 ms 344 KB #experiments: 2
2 Correct 1 ms 344 KB #experiments: 3
3 Correct 0 ms 344 KB #experiments: 3
4 Correct 1 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 0 ms 344 KB #experiments: 2
3 Correct 1 ms 344 KB #experiments: 3
4 Correct 0 ms 344 KB #experiments: 3
5 Correct 1 ms 344 KB #experiments: 4
6 Correct 6 ms 344 KB #experiments: 260
7 Correct 4 ms 344 KB #experiments: 298
8 Correct 4 ms 344 KB #experiments: 305
9 Correct 4 ms 428 KB #experiments: 294
10 Correct 6 ms 344 KB #experiments: 296
11 Correct 3 ms 344 KB #experiments: 294
12 Correct 5 ms 344 KB #experiments: 299
13 Correct 4 ms 344 KB #experiments: 294
14 Correct 4 ms 596 KB #experiments: 283
15 Correct 6 ms 344 KB #experiments: 279
16 Correct 5 ms 344 KB #experiments: 283
17 Correct 5 ms 344 KB #experiments: 279
18 Correct 7 ms 344 KB #experiments: 282
19 Correct 5 ms 344 KB #experiments: 284
20 Correct 6 ms 344 KB #experiments: 288
21 Correct 4 ms 344 KB #experiments: 287
22 Correct 6 ms 344 KB #experiments: 290
23 Correct 4 ms 436 KB #experiments: 260
24 Correct 7 ms 344 KB #experiments: 309
25 Correct 7 ms 344 KB #experiments: 338
26 Correct 5 ms 348 KB #experiments: 286
27 Correct 4 ms 344 KB #experiments: 289
28 Correct 5 ms 344 KB #experiments: 301
29 Correct 6 ms 344 KB #experiments: 341
30 Correct 9 ms 348 KB #experiments: 372
31 Correct 8 ms 352 KB #experiments: 291
32 Correct 7 ms 356 KB #experiments: 288
33 Correct 4 ms 356 KB #experiments: 238
34 Correct 7 ms 348 KB #experiments: 290

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 2
2 Correct 1 ms 344 KB #experiments: 3
3 Correct 0 ms 344 KB #experiments: 3
4 Correct 1 ms 344 KB #experiments: 4
5 Correct 6 ms 344 KB #experiments: 260
6 Correct 4 ms 344 KB #experiments: 298
7 Correct 4 ms 344 KB #experiments: 305
8 Correct 4 ms 428 KB #experiments: 294
9 Correct 6 ms 344 KB #experiments: 296
10 Correct 3 ms 344 KB #experiments: 294
11 Correct 5 ms 344 KB #experiments: 299
12 Correct 4 ms 344 KB #experiments: 294
13 Correct 238 ms 592 KB #experiments: 2008
14 Correct 228 ms 484 KB #experiments: 2038
15 Correct 252 ms 720 KB #experiments: 2068
16 Correct 265 ms 728 KB #experiments: 2106
17 Correct 262 ms 720 KB #experiments: 2150
18 Correct 265 ms 728 KB #experiments: 2146
19 Correct 263 ms 480 KB #experiments: 2136
20 Correct 230 ms 728 KB #experiments: 1811
21 Correct 260 ms 600 KB #experiments: 2136

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 2
2 Correct 1 ms 344 KB #experiments: 3
3 Correct 0 ms 344 KB #experiments: 3
4 Correct 1 ms 344 KB #experiments: 4
5 Correct 4 ms 596 KB #experiments: 283
6 Correct 6 ms 344 KB #experiments: 279
7 Correct 5 ms 344 KB #experiments: 283
8 Correct 5 ms 344 KB #experiments: 279
9 Correct 7 ms 344 KB #experiments: 282
10 Correct 5 ms 344 KB #experiments: 284
11 Correct 6 ms 344 KB #experiments: 288
12 Correct 4 ms 344 KB #experiments: 287
13 Correct 323 ms 856 KB #experiments: 1990
14 Correct 342 ms 856 KB #experiments: 1998
15 Correct 296 ms 856 KB #experiments: 1991
16 Correct 334 ms 924 KB #experiments: 1999
17 Correct 284 ms 856 KB #experiments: 1995
18 Correct 285 ms 856 KB #experiments: 1997
19 Correct 324 ms 856 KB #experiments: 1993
20 Correct 318 ms 856 KB #experiments: 1993
21 Correct 304 ms 856 KB #experiments: 1997

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 8
2 Correct 0 ms 344 KB #experiments: 2
3 Correct 1 ms 344 KB #experiments: 3
4 Correct 0 ms 344 KB #experiments: 3
5 Correct 1 ms 344 KB #experiments: 4
6 Correct 6 ms 344 KB #experiments: 260
7 Correct 4 ms 344 KB #experiments: 298
8 Correct 4 ms 344 KB #experiments: 305
9 Correct 4 ms 428 KB #experiments: 294
10 Correct 6 ms 344 KB #experiments: 296
11 Correct 3 ms 344 KB #experiments: 294
12 Correct 5 ms 344 KB #experiments: 299
13 Correct 4 ms 344 KB #experiments: 294
14 Correct 4 ms 596 KB #experiments: 283
15 Correct 6 ms 344 KB #experiments: 279
16 Correct 5 ms 344 KB #experiments: 283
17 Correct 5 ms 344 KB #experiments: 279
18 Correct 7 ms 344 KB #experiments: 282
19 Correct 5 ms 344 KB #experiments: 284
20 Correct 6 ms 344 KB #experiments: 288
21 Correct 4 ms 344 KB #experiments: 287
22 Correct 6 ms 344 KB #experiments: 290
23 Correct 4 ms 436 KB #experiments: 260
24 Correct 7 ms 344 KB #experiments: 309
25 Correct 7 ms 344 KB #experiments: 338
26 Correct 5 ms 348 KB #experiments: 286
27 Correct 4 ms 344 KB #experiments: 289
28 Correct 5 ms 344 KB #experiments: 301
29 Correct 6 ms 344 KB #experiments: 341
30 Correct 9 ms 348 KB #experiments: 372
31 Correct 8 ms 352 KB #experiments: 291
32 Correct 7 ms 356 KB #experiments: 288
33 Correct 4 ms 356 KB #experiments: 238
34 Correct 7 ms 348 KB #experiments: 290
35 Correct 238 ms 592 KB #experiments: 2008
36 Correct 228 ms 484 KB #experiments: 2038
37 Correct 252 ms 720 KB #experiments: 2068
38 Correct 265 ms 728 KB #experiments: 2106
39 Correct 262 ms 720 KB #experiments: 2150
40 Correct 265 ms 728 KB #experiments: 2146
41 Correct 263 ms 480 KB #experiments: 2136
42 Correct 230 ms 728 KB #experiments: 1811
43 Correct 260 ms 600 KB #experiments: 2136
44 Correct 323 ms 856 KB #experiments: 1990
45 Correct 342 ms 856 KB #experiments: 1998
46 Correct 296 ms 856 KB #experiments: 1991
47 Correct 334 ms 924 KB #experiments: 1999
48 Correct 284 ms 856 KB #experiments: 1995
49 Correct 285 ms 856 KB #experiments: 1997
50 Correct 324 ms 856 KB #experiments: 1993
51 Correct 318 ms 856 KB #experiments: 1993
52 Correct 304 ms 856 KB #experiments: 1997
53 Incorrect 374 ms 736 KB #experiments reached 2751
54 Halted 0 ms 0 KB -