oj.uz

Submission #393473

# Submission time Handle Problem Language Result Execution time Memory
393473 2021-04-23T14:41:20 Z usachevd0 Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 3 ms 588 KB 
#include <bits/stdc++.h>
#ifndef DEBUG
  #include "messy.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
  return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
  return y > x ? (x = y, true) : false;
}
void debug_out() {
  cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
  cerr << ' ' << A;
  debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
  for (int i = 0; i < n; ++i) cerr << a[i];
  cerr << endl;
}
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
  for (auto& x : v) {
    stream << x << ' ';
  }
  return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
  return stream << p.first << ' ' << p.second;
}

#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif


#ifdef DEBUG
  int n, W, R;
  vector<int> p;
  set<string> S;

  void add_element(string s) {
    assert(--W >= 0);
    string t(n, '?');
    for (int i = 0; i < n; ++i) {
      t[i] = s[p[i]];
    }
//    debug(s);
//    debug(t);
    S.insert(t);
  }
  void compile_set() {
  }
  bool check_element(string s) {
    assert(--R >= 0);
    return S.count(s);
  }
#endif

char inv(char c) {
  return '1' - c + '0';
}

vector<int> restore_permutation(int n, int W, int R) {
  int k = 0;
  while ((1 << k) < n) ++k;

  string M(n, '0');
  for (int j = 0; j < k - 1; ++j) {
    string newM(all(M));
    for (int i = 0; i < n; ++i) {
      if ((i >> j) & 1) {
        string q(all(M));
        q[i] = inv(q[i]);
        add_element(q);
        newM[i] = '1';
      }
    }
    swap(M, newM);
//    debug(M);
  }
  for (int i = n / 2; i < n; ++i) {
    string q(n, '1');
    q[i] = '0';
    add_element(q);
  }
  compile_set();

  vector<vector<char>> A(k, vector<char>(n, false));
  M = string(n, '0');
  for (int j = 0; j < k - 1; ++j) {
    string newM(all(M));
    for (int i = 0; i < n; ++i) {
      string q(all(M));
      q[i] = inv(q[i]);
      if (check_element(q)) {
        A[j][i] = true;
        newM[i] = '1';
      }
    }
    swap(M, newM);
  }
  for (int i = 0; i < n; ++i) {
    string q(n, '1');
    q[i] = '0';
    if (check_element(q)) {
      A[k - 1][i] = true;
    }
  }

  vector<int> p(n);
  for (int x = 0; x < n; ++x) {
    vector<char> mask(n, true);
    for (int j = 0; j < k; ++j) {
      for (int i = 0; i < n; ++i) {
        mask[i] &= A[j][i] == ((x >> j) & 1);
      }
    }
    assert(count(all(mask), true) == 1);
    int i = find(all(mask), true) - mask.begin();
    p[i] = x;
  }
  return p;
}

#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  mt19937 rng(228);
  for (int itr = 1; ; ++itr) {
    n = 8;
    int k = 0;
    while ((1 << k) < n) ++k;
    W = k * n;
    R = k * n;
    p.resize(n);
    iota(all(p), 0);
    shuffle(all(p), rng);
    //debug(p);
    S.clear();
    if (restore_permutation(n, W, R) != p) {
      cerr << "BAD";
      exit(0);
    }
    debug(itr);
  }

  return 0;
}
#endif

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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