oj.uz

Submission #1099900

# Submission time Handle Problem Language Result Execution time Memory
1099900 2024-10-12T05:47:52 Z model_code Sphinx's Riddle (IOI24_sphinx) C++17
24 / 100
 69 ms 912 KB 
// correct/subtask4.cpp

#include "sphinx.h"

using namespace std;

vector<int> find_colours(int N, vector<int> /*X*/, vector<int> /*Y*/) {
  vector<vector<int>> comps;
  comps.push_back({0});
  vector<int> ord(N);
  for (int i = 1; i < N; ++i) {
    ord.assign(N, -1);
    for (int j = i + 1; j < N; ++j) ord[j] = N;
    if (perform_experiment(ord) == (int)comps.size() + 1 + (i + 1 < N)) {
      comps.push_back({i});
      continue;
    }

    int lo = 0, hi = comps.size();
    while (lo + 1 < hi) {
      int mid = (lo + hi) / 2;
      ord.assign(N, N);
      ord[i] = -1;
      for (int c = mid; c < hi; ++c) {
        for (int u : comps[c]) ord[u] = -1;
      }
      int expected = 2 + hi - mid;
      if (perform_experiment(ord) < expected) {
        lo = mid;
      } else {
        hi = mid;
      }
    }
    comps[lo].push_back(i);
  }

  int n = comps.size();
  vector<int> comp_factions(n, -1);
  for (int f = 0; f < N; ++f) {
    ord.assign(N, f);
    ord[0] = -1;
    if (perform_experiment(ord) == 1) {
      comp_factions[0] = f;
      break;
    }
  }
  for (int f = 0; f < N; ++f) {
    ord.assign(N, -1);
    for (int u : comps[0]) ord[u] = f;
    if (perform_experiment(ord) == n) continue;

    int lo = 1, hi = n;
    while (lo + 1 < hi) {
      int mid = (lo + hi) / 2;
      ord.assign(N, f);
      for (int c = mid; c < hi; ++c) {
        for (int u : comps[c]) ord[u] = -1;
      }
      int expected = hi - mid + 1;
      if (perform_experiment(ord) < expected) {
        lo = mid;
      } else {
        hi = mid;
      }
    }
    comp_factions[lo] = f;
  }

  vector<int> F(N, -1);
  for (int c = 0; c < n; ++c) {
    for (int u : comps[c]) {
      F[u] = comp_factions[c];
    }
  }
  return F;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Invalid value of G[2]: -1
2 Halted 0 ms 0 KB -

Subtask #1
3.0 / 3.0

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

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Invalid value of G[2]: -1
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 4
2 Correct 0 ms 344 KB #experiments: 4
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 5
5 Correct 1 ms 344 KB #experiments: 124
6 Incorrect 2 ms 344 KB Invalid value of G[37]: -1
7 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 4
2 Correct 0 ms 344 KB #experiments: 4
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 5
5 Correct 2 ms 344 KB #experiments: 114
6 Correct 2 ms 344 KB #experiments: 228
7 Correct 3 ms 344 KB #experiments: 246
8 Correct 3 ms 344 KB #experiments: 286
9 Correct 2 ms 344 KB #experiments: 340
10 Correct 4 ms 344 KB #experiments: 334
11 Correct 4 ms 444 KB #experiments: 383
12 Correct 5 ms 344 KB #experiments: 413
13 Correct 25 ms 856 KB #experiments: 903
14 Correct 39 ms 888 KB #experiments: 1378
15 Correct 41 ms 884 KB #experiments: 1688
16 Correct 54 ms 856 KB #experiments: 1910
17 Correct 64 ms 912 KB #experiments: 2139
18 Correct 69 ms 908 KB #experiments: 2327
19 Correct 68 ms 900 KB #experiments: 2329
20 Correct 18 ms 864 KB #experiments: 559
21 Correct 62 ms 856 KB #experiments: 2524

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Invalid value of G[2]: -1
2 Halted 0 ms 0 KB -