oj.uz

Submission #299812

# Submission time Handle Problem Language Result Execution time Memory
299812 2020-09-15T17:58:24 Z Tangent Mechanical Doll (IOI18_doll) C++17
100 / 100
 285 ms 23488 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// find_by_order(), order_of_key()

typedef long long ll;
typedef long double dd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<dd, dd> pdd;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<dd> vdd;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdd;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vdd> vvdd;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef vector<vpdd> vvpdd;
typedef vector<bool> vb;

const int inf = 1 << 30;

#define rep(i, n) for (ll i = 0; i < n; i++)
#define ffor(i, a, b) for(ll i = a; i < b; i++)
#define forin(x, a) for (auto &x: a)
#define all(x) x.begin(), x.end()


#ifdef TEST
#define dbg(x) cout << #x << ": " << x << '\n';
#define dbgc(x) cout << #x << ":"; forin(a, x) { cout << " " << a; } cout << endl;
#define tassert(x) assert(x);
#else
#define dbg(x)
#define dbgc(x)
#define tassert(x)
#endif

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  map<int, int> counts;
  int max_count = 0;
  forin(x, A) {
    counts[x]++;
    max_count = max(max_count, counts[x]);
  }

  vii C(M + 1);
  if (max_count == 1) {
    rep(i, N - 1) {
      C[A[i]] = A[i + 1];
    }
    C[0] = A[0];
    C[A[N - 1]] = 0;
    answer(C, vii(), vii());
  } else {
    C.assign(M + 1, -1);
    int p2 = 1, bits = 0;
    while (p2 < N + 1) {
      p2 <<= 1;
      bits++;
    }
    int curr = 0;
    map<int, int> order;
    rep(i, p2) {
      if (i >= p2 - N - 1)
        order[curr] = i;
      int x = 1 << (bits - 1);
      while (curr & x) {
        curr ^= x;
        x >>= 1;
      }
      curr ^= x;
    }
    int j = 0;
    vii seq(p2, -1);
    forin(p, order) {
      seq[p.second] = j++;
    }
    int l = p2;
    vii above = {0}, X, Y;
    rep(d, bits) {
      vii nabove;
      rep(i, 1 << d) {
        if (above[i >> 1] == -1) {
          nabove.emplace_back(-1);
        } else if (l * (i + 1) <= p2 - N - 1) {
          nabove.emplace_back(-1);
          if (i & 1) {
            Y[above[i >> 1]] = -1;
          } else {
            X[above[i >> 1]] = -1;
          }
        } else {
          X.emplace_back(-1);
          Y.emplace_back(-1);
          nabove.emplace_back(X.size() - 1);
          if (i & 1) {
            Y[above[i >> 1]] = -X.size();
          } else {
            X[above[i >> 1]] = -X.size();
          }
        }
      }
      above = move(nabove);
      l >>= 1;
    }
    A.emplace_back(0);
    rep(i, p2) {
      if (seq[i] >= 0) {
        if (i & 1) {
          Y[above[i >> 1]] = A[seq[i]];
        } else {
          X[above[i >> 1]] = A[seq[i]];
        }
      }
    }

    answer(C, X, Y);
  }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 60 ms 4980 KB Output is correct
3 Correct 55 ms 4560 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 75 ms 6928 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 60 ms 4980 KB Output is correct
3 Correct 55 ms 4560 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 75 ms 6928 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 168 ms 15912 KB Output is correct
9 Correct 191 ms 17352 KB Output is correct
10 Correct 282 ms 23488 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 60 ms 4980 KB Output is correct
3 Correct 55 ms 4560 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 75 ms 6928 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 168 ms 15912 KB Output is correct
9 Correct 191 ms 17352 KB Output is correct
10 Correct 282 ms 23488 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 264 ms 21608 KB Output is correct
15 Correct 161 ms 13944 KB Output is correct
16 Correct 263 ms 20456 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 263 ms 22208 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 121 ms 12048 KB Output is correct
3 Correct 95 ms 12096 KB Output is correct
4 Correct 176 ms 17532 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 121 ms 12048 KB Output is correct
3 Correct 95 ms 12096 KB Output is correct
4 Correct 176 ms 17532 KB Output is correct
5 Correct 253 ms 19972 KB Output is correct
6 Correct 277 ms 18832 KB Output is correct
7 Correct 231 ms 19012 KB Output is correct
8 Correct 274 ms 18308 KB Output is correct
9 Correct 100 ms 12052 KB Output is correct
10 Correct 242 ms 17980 KB Output is correct
11 Correct 214 ms 17660 KB Output is correct
12 Correct 149 ms 12044 KB Output is correct
13 Correct 164 ms 12964 KB Output is correct
14 Correct 185 ms 13224 KB Output is correct
15 Correct 163 ms 13604 KB Output is correct
16 Correct 3 ms 716 KB Output is correct
17 Correct 151 ms 11920 KB Output is correct
18 Correct 115 ms 12116 KB Output is correct
19 Correct 141 ms 12040 KB Output is correct
20 Correct 251 ms 17816 KB Output is correct
21 Correct 197 ms 17660 KB Output is correct
22 Correct 285 ms 17672 KB Output is correct