oj.uz

답안 #1099913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1099913 2024-10-12T05:50:25 Z model_code 스핑크스 (IOI24_sphinx) C++17
64 / 100
 748 ms 928 KB 
// failed/GA_heuristic_improved.cpp

#include <algorithm>
#include <random>

#include "sphinx.h"

using namespace std;

const int MIN_DEG = 25;
const int ATTEMPTS = 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) {
  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> indep2;
    int best_color = -1;
    int best_count = 0;
    for (int i = 0; i < ATTEMPTS; i++) {
      vector<int> indep = find_indep(remaining);
      int best_color0 = -1;
      int best_count0 = best_count;
      for (int i = 0; i < N; i++) {
        int count = 0;
        for (int j : indep) {
          if (possible_colors[j][i]) {
            count++;
          }
        }
        if (count > best_count0) {
          best_count0 = count;
          best_color0 = i;
        }
      }
      if (best_count0 > best_count) {
        best_color = best_color0;
        best_count = best_count0;
        indep2.clear();
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB #experiments: 8

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB #experiments: 2
2 Correct 0 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

# 결과 실행 시간 메모리 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 344 KB #experiments: 3
5 Correct 1 ms 344 KB #experiments: 4
6 Correct 6 ms 344 KB #experiments: 245
7 Correct 13 ms 432 KB #experiments: 294
8 Correct 8 ms 432 KB #experiments: 298
9 Correct 12 ms 436 KB #experiments: 296
10 Correct 8 ms 344 KB #experiments: 291
11 Correct 8 ms 432 KB #experiments: 294
12 Correct 6 ms 344 KB #experiments: 287
13 Correct 6 ms 344 KB #experiments: 290
14 Correct 4 ms 344 KB #experiments: 286
15 Correct 8 ms 348 KB #experiments: 287
16 Correct 5 ms 348 KB #experiments: 290
17 Correct 7 ms 344 KB #experiments: 283
18 Correct 4 ms 344 KB #experiments: 287
19 Correct 6 ms 344 KB #experiments: 275
20 Correct 6 ms 344 KB #experiments: 285
21 Correct 4 ms 344 KB #experiments: 286
22 Correct 11 ms 344 KB #experiments: 307
23 Correct 6 ms 344 KB #experiments: 283
24 Correct 7 ms 344 KB #experiments: 290
25 Correct 8 ms 436 KB #experiments: 257
26 Correct 13 ms 344 KB #experiments: 291
27 Correct 11 ms 428 KB #experiments: 297
28 Correct 10 ms 348 KB #experiments: 298
29 Correct 8 ms 440 KB #experiments: 318
30 Correct 9 ms 344 KB #experiments: 358
31 Correct 6 ms 348 KB #experiments: 286
32 Correct 4 ms 344 KB #experiments: 290
33 Correct 8 ms 352 KB #experiments: 242
34 Correct 5 ms 352 KB #experiments: 292

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB #experiments: 2
2 Correct 0 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: 245
6 Correct 13 ms 432 KB #experiments: 294
7 Correct 8 ms 432 KB #experiments: 298
8 Correct 12 ms 436 KB #experiments: 296
9 Correct 8 ms 344 KB #experiments: 291
10 Correct 8 ms 432 KB #experiments: 294
11 Correct 6 ms 344 KB #experiments: 287
12 Correct 6 ms 344 KB #experiments: 290
13 Correct 630 ms 472 KB #experiments: 2045
14 Correct 748 ms 484 KB #experiments: 2052
15 Correct 628 ms 480 KB #experiments: 2079
16 Correct 702 ms 480 KB #experiments: 2109
17 Correct 612 ms 476 KB #experiments: 2124
18 Correct 642 ms 712 KB #experiments: 2065
19 Correct 548 ms 484 KB #experiments: 2123
20 Correct 501 ms 464 KB #experiments: 1814
21 Correct 574 ms 732 KB #experiments: 2084

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB #experiments: 2
2 Correct 0 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 344 KB #experiments: 286
6 Correct 8 ms 348 KB #experiments: 287
7 Correct 5 ms 348 KB #experiments: 290
8 Correct 7 ms 344 KB #experiments: 283
9 Correct 4 ms 344 KB #experiments: 287
10 Correct 6 ms 344 KB #experiments: 275
11 Correct 6 ms 344 KB #experiments: 285
12 Correct 4 ms 344 KB #experiments: 286
13 Correct 273 ms 856 KB #experiments: 1993
14 Correct 383 ms 856 KB #experiments: 1995
15 Correct 343 ms 856 KB #experiments: 1991
16 Correct 280 ms 856 KB #experiments: 1997
17 Correct 291 ms 856 KB #experiments: 1993
18 Correct 293 ms 928 KB #experiments: 1998
19 Correct 273 ms 856 KB #experiments: 1996
20 Correct 313 ms 856 KB #experiments: 1990
21 Correct 286 ms 856 KB #experiments: 1998

Subtask #5
0.0 / 36.0

# 결과 실행 시간 메모리 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 344 KB #experiments: 3
5 Correct 1 ms 344 KB #experiments: 4
6 Correct 6 ms 344 KB #experiments: 245
7 Correct 13 ms 432 KB #experiments: 294
8 Correct 8 ms 432 KB #experiments: 298
9 Correct 12 ms 436 KB #experiments: 296
10 Correct 8 ms 344 KB #experiments: 291
11 Correct 8 ms 432 KB #experiments: 294
12 Correct 6 ms 344 KB #experiments: 287
13 Correct 6 ms 344 KB #experiments: 290
14 Correct 4 ms 344 KB #experiments: 286
15 Correct 8 ms 348 KB #experiments: 287
16 Correct 5 ms 348 KB #experiments: 290
17 Correct 7 ms 344 KB #experiments: 283
18 Correct 4 ms 344 KB #experiments: 287
19 Correct 6 ms 344 KB #experiments: 275
20 Correct 6 ms 344 KB #experiments: 285
21 Correct 4 ms 344 KB #experiments: 286
22 Correct 11 ms 344 KB #experiments: 307
23 Correct 6 ms 344 KB #experiments: 283
24 Correct 7 ms 344 KB #experiments: 290
25 Correct 8 ms 436 KB #experiments: 257
26 Correct 13 ms 344 KB #experiments: 291
27 Correct 11 ms 428 KB #experiments: 297
28 Correct 10 ms 348 KB #experiments: 298
29 Correct 8 ms 440 KB #experiments: 318
30 Correct 9 ms 344 KB #experiments: 358
31 Correct 6 ms 348 KB #experiments: 286
32 Correct 4 ms 344 KB #experiments: 290
33 Correct 8 ms 352 KB #experiments: 242
34 Correct 5 ms 352 KB #experiments: 292
35 Correct 630 ms 472 KB #experiments: 2045
36 Correct 748 ms 484 KB #experiments: 2052
37 Correct 628 ms 480 KB #experiments: 2079
38 Correct 702 ms 480 KB #experiments: 2109
39 Correct 612 ms 476 KB #experiments: 2124
40 Correct 642 ms 712 KB #experiments: 2065
41 Correct 548 ms 484 KB #experiments: 2123
42 Correct 501 ms 464 KB #experiments: 1814
43 Correct 574 ms 732 KB #experiments: 2084
44 Correct 273 ms 856 KB #experiments: 1993
45 Correct 383 ms 856 KB #experiments: 1995
46 Correct 343 ms 856 KB #experiments: 1991
47 Correct 280 ms 856 KB #experiments: 1997
48 Correct 291 ms 856 KB #experiments: 1993
49 Correct 293 ms 928 KB #experiments: 1998
50 Correct 273 ms 856 KB #experiments: 1996
51 Correct 313 ms 856 KB #experiments: 1990
52 Correct 286 ms 856 KB #experiments: 1998
53 Incorrect 660 ms 752 KB #experiments reached 2751
54 Halted 0 ms 0 KB -