oj.uz

Submission #258405

# Submission time Handle Problem Language Result Execution time Memory
258405 2020-08-05T22:35:29 Z ipaljak Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 3 ms 640 KB 
#include "messy.h"

#include <bits/stdc++.h>

using namespace std;

#define TRACE(x) cerr << #x << " " << x << endl
#define _ << " " <<

void add_elements(int lo, int hi, int n) {
  if (lo + 1 == hi) return;
  string s(n, '0');
  for (int i = 0; i < n; ++i)
    if (i < lo || i >= hi) s[i] = '1';
  for (int i = lo; i < (lo + hi) / 2; ++i) {
    s[i] = '1';
    add_element(s);
    s[i] = '0';
  }
  add_elements(lo, (lo + hi) / 2, n);
  add_elements((lo + hi) / 2, hi, n);
}

void solve(int lo, int hi, int n, const set<int> &target, vector<int> &p) {
  assert(hi - lo == (int) target.size());
  if (lo + 1 == hi) {
    p[*target.begin()] = lo;
    return;
  }

  string s(n, '0');
  for (int i = 0; i < n; ++i)
    if (target.find(i) == target.end())
      s[i] = '1';

  set<int> a, b;
  for (int x : target) {
    s[x] = '1';
    bool flag = check_element(s);
    s[x] = '0';
    if (flag) a.insert(x); else b.insert(x);
  }

  assert(a.size() == b.size());

  solve(lo, (lo + hi) / 2, n, a, p);
  solve((lo + hi) / 2, hi, n, b, p);
}

vector<int> restore_permutation(int n, int w, int r) {
  add_elements(0, n, n);
  compile_set();
  vector<int> ret(n);
  set<int> dest;
  for (int i = 0; i < n; ++i) dest.insert(i);
  solve(0, n, n, dest, ret);
  return ret;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB n = 8
2 Correct 1 ms 256 KB n = 8
3 Correct 1 ms 256 KB n = 8
4 Correct 1 ms 256 KB n = 8
5 Correct 0 ms 256 KB n = 8
6 Correct 1 ms 256 KB n = 8
7 Correct 1 ms 384 KB n = 8
8 Correct 0 ms 256 KB n = 8
9 Correct 0 ms 256 KB n = 8
10 Correct 0 ms 256 KB n = 8
11 Correct 0 ms 256 KB n = 8
12 Correct 1 ms 256 KB n = 8
13 Correct 1 ms 256 KB n = 8
14 Correct 0 ms 256 KB n = 8
15 Correct 0 ms 256 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 32
2 Correct 1 ms 384 KB n = 32
3 Correct 1 ms 384 KB n = 32
4 Correct 1 ms 384 KB n = 32
5 Correct 1 ms 384 KB n = 32
6 Correct 1 ms 384 KB n = 32
7 Correct 1 ms 384 KB n = 32
8 Correct 1 ms 384 KB n = 32
9 Correct 1 ms 384 KB n = 32
10 Correct 1 ms 384 KB n = 32
11 Correct 1 ms 384 KB n = 32
12 Correct 1 ms 384 KB n = 32
13 Correct 1 ms 384 KB n = 32
14 Correct 1 ms 384 KB n = 32
15 Correct 1 ms 384 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 32
2 Correct 1 ms 384 KB n = 32
3 Correct 1 ms 384 KB n = 32
4 Correct 1 ms 384 KB n = 32
5 Correct 1 ms 384 KB n = 32
6 Correct 1 ms 384 KB n = 32
7 Correct 0 ms 384 KB n = 32
8 Correct 1 ms 384 KB n = 32
9 Correct 1 ms 384 KB n = 32
10 Correct 1 ms 384 KB n = 32
11 Correct 1 ms 384 KB n = 32
12 Correct 1 ms 368 KB n = 32
13 Correct 1 ms 384 KB n = 32
14 Correct 1 ms 384 KB n = 32
15 Correct 1 ms 384 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB n = 128
2 Correct 2 ms 512 KB n = 128
3 Correct 2 ms 512 KB n = 128
4 Correct 2 ms 512 KB n = 128
5 Correct 3 ms 512 KB n = 128
6 Correct 2 ms 512 KB n = 128
7 Correct 2 ms 512 KB n = 128
8 Correct 2 ms 512 KB n = 128
9 Correct 2 ms 512 KB n = 128
10 Correct 2 ms 512 KB n = 128
11 Correct 2 ms 512 KB n = 128
12 Correct 2 ms 512 KB n = 128
13 Correct 2 ms 512 KB n = 128
14 Correct 2 ms 512 KB n = 128
15 Correct 2 ms 512 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB n = 128
2 Correct 2 ms 512 KB n = 128
3 Correct 2 ms 512 KB n = 128
4 Correct 2 ms 512 KB n = 128
5 Correct 2 ms 512 KB n = 128
6 Correct 2 ms 512 KB n = 128
7 Correct 2 ms 512 KB n = 128
8 Correct 2 ms 512 KB n = 128
9 Correct 2 ms 512 KB n = 128
10 Correct 2 ms 512 KB n = 128
11 Correct 2 ms 512 KB n = 128
12 Correct 2 ms 512 KB n = 128
13 Correct 2 ms 512 KB n = 128
14 Correct 2 ms 512 KB n = 128
15 Correct 2 ms 512 KB n = 128