oj.uz

Submission #1099902

# Submission time Handle Problem Language Result Execution time Memory
1099902 2024-10-12T05:48:16 Z model_code Sphinx's Riddle (IOI24_sphinx) C++17
36 / 100
 53 ms 352 KB 
// correct/subtask3-author.cpp

#include <bits/stdc++.h>

#include "sphinx.h"
using namespace std;

#ifdef DEBUG
#define D(x...) fprintf(stderr, x)
#define DA(x) assert(x)
#else
#define D(x...)
#define DA(x)
#endif

const int MAX_N = 250 + 10;

int ans[MAX_N];
vector<int> mask;

int n;

// range is [s, e)
// parity is 0 or 1
int do_query(int s, int e, int parity, int color) {
  fill(mask.begin(), mask.end(), n);

  int ss = s;
  if ((s & 1) == parity) {
    ss--;
  }
  int ee = e;
  if ((e & 1) == parity) {
    ee--;
  }
  D("querying [%d, %d) with:", s, e);
  for (int i = max(0, ss); i <= min(n - 1, ee); i++) {
    if ((i & 1) == parity) {
      mask[i] = -1;
    } else {
      mask[i] = color;
    }
    D(" %d", mask[i]);
  }
  int if_none = 1;
  for (int i = 1; i < n; i++) {
    if (mask[i - 1] != mask[i]) {
      if_none++;
    }
  }

  int res = perform_experiment(mask);
  int delta = if_none - res;
  D(" -> delta=%d [result %d, %d if none]\n", delta, res, if_none);

  return delta;
}

// invariant: delta > 0
// finds all of color in this range (for this parity), and marks them in ans
void go(int s, int e, int parity, int color, int delta) {
  D("go([%d, %d), parity=%d, color=%d, delta=%d)\n", s, e, parity, color,
    delta);
  DA(delta > 0);

  // Handle 0 or 1 elements in range.
  int ss = s;
  if ((s & 1) != parity) {
    ss++;
  }
  if (ss >= e) return;
  if (ss + 2 >= e) {
    ans[ss] = color;
    D("! identified %d as %d\n", ss, color);
    return;
  }

  int mid = (s + e) / 2;

  // TODO: optimize dr call.
  int dl = do_query(s, mid, parity, color);
  /*
  int dr = do_query(mid, e, parity, color);
  DA(dl + dr == delta);
  */
  int dr = delta - dl;

  if (dl) {
    go(s, mid, parity, color, dl);
  }
  if (dr) {
    go(mid, e, parity, color, dr);
  }
}

vector<int> find_colours(int _n, vector<int> /*a*/, vector<int> /*b*/) {
  n = _n;
  mask.resize(n);

  for (int c = 0; c < n; c++) {
    for (int z = 0; z < 2; z++) {
      int delta = do_query(0, n, z, c);
      if (delta) {
        go(0, n, z, c, delta);
      }
    }
  }

  return vector<int>(ans, ans + n);
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Vertices 1 and 2 do have the same color, but they do not in returned answer
2 Halted 0 ms 0 KB -

Subtask #1
3.0 / 3.0

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

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Vertices 1 and 2 do have the same color, but they do not in returned answer
2 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB #experiments: 4
2 Correct 0 ms 344 KB #experiments: 4
3 Correct 0 ms 344 KB #experiments: 4
4 Correct 0 ms 344 KB #experiments: 4
5 Correct 3 ms 344 KB #experiments: 148
6 Correct 2 ms 352 KB #experiments: 160
7 Correct 2 ms 352 KB #experiments: 176
8 Correct 2 ms 352 KB #experiments: 182
9 Correct 2 ms 352 KB #experiments: 212
10 Correct 3 ms 344 KB #experiments: 241
11 Correct 3 ms 348 KB #experiments: 319
12 Correct 5 ms 344 KB #experiments: 336
13 Correct 23 ms 344 KB #experiments: 760
14 Correct 16 ms 344 KB #experiments: 784
15 Correct 15 ms 344 KB #experiments: 855
16 Correct 16 ms 344 KB #experiments: 915
17 Correct 29 ms 344 KB #experiments: 1246
18 Correct 28 ms 340 KB #experiments: 1675
19 Correct 41 ms 344 KB #experiments: 2072
20 Correct 16 ms 344 KB #experiments: 748
21 Correct 53 ms 344 KB #experiments: 2244

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB #experiments: 4
2 Correct 0 ms 344 KB #experiments: 4
3 Correct 0 ms 344 KB #experiments: 4
4 Correct 0 ms 344 KB #experiments: 4
5 Incorrect 19 ms 344 KB Vertices 0 and 1 do have the same color, but they do not in returned answer
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Vertices 1 and 2 do have the same color, but they do not in returned answer
2 Halted 0 ms 0 KB -