oj.uz

Submission #767353

# Submission time Handle Problem Language Result Execution time Memory
767353 2023-06-26T16:34:31 Z marvinthang Mechanical Doll (IOI18_doll) C++17
100 / 100
 77 ms 11208 KB 
/*************************************
*    author: marvinthang             *
*    created: 26.06.2023 22:53:11    *
*************************************/

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

int N, M;
vector <int> A, X, Y;

void gen_tree(int cur, int k, int v) {
    if (k == 1) {
        X[cur] = 0;
        Y[cur] = v == 2 ? 0 : -1;
        return;
    }
    int r;
    if (v <= MASK(k - 1)) {
        r = 0;
    } else {
        r = X.size();
        X.push_back(0);
        Y.push_back(0);
        gen_tree(r, k - 1, MASK(k - 1));
        v -= MASK(k - 1);
    }
    int l = X.size();
    X.push_back(0);
    Y.push_back(0);
    gen_tree(l, k - 1, v);
    X[cur] = -1 - l;
    Y[cur] = -1 - r;
}

void dfs(int u) {
    if (A.empty()) return;
    u = -u - 1;
    swap(X[u], Y[u]);
    if (!Y[u]) {
        Y[u] = A.back();
        A.pop_back();
        dfs(-1);
    } else dfs(Y[u]);
}

void create_circuit(int m, vector<int> a) {
    A = a; M = m;
    A.push_back(0);
    reverse(ALL(A));
    N = A.size();
    int k = 1;
    while (MASK(k) < N) ++k;
    X.push_back(0);
    Y.push_back(0);
    gen_tree(0, k, N);
    vector <int> C(M + 1, -1);
    dfs(-1);
    answer(C, X, Y);
}

#ifdef LOCAL
#include <cstdio>
#include <cstdlib>
#include "doll.h"

namespace {

constexpr int P_MAX = 20000000;
constexpr int S_MAX = 400000;

int ___M, ___N;
std::vector<int> ___A;

bool answered;
int S;
std::vector<int> IC, IX, IY;

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

void wrong_answer(const char *MSG) {
  printf("Wrong Answer: %s\n", MSG);
  exit(0);
}

void simulate() {
  if (S > S_MAX) {
    char str[50];
    sprintf(str, "over %d switches", S_MAX);
    wrong_answer(str);
  }
  for (int i = 0; i <= ___M; ++i) {
    if (!(-S <= IC[i] && IC[i] <= ___M)) {
      wrong_answer("wrong serial number");
    }
  }
  for (int j = 1; j <= S; ++j) {
    if (!(-S <= IX[j - 1] && IX[j - 1] <= ___M)) {
      wrong_answer("wrong serial number");
    }
    if (!(-S <= IY[j - 1] && IY[j - 1] <= ___M)) {
      wrong_answer("wrong serial number");
    }
  }

  int P = 0;
  std::vector<bool> state(S + 1, false);
  int pos = IC[0];
  int k = 0;
  FILE *file_log = fopen("log.txt", "w");
  fprintf(file_log, "0\n");
  for (;;) {
    fprintf(file_log, "%d\n", pos);
    if (pos < 0) {
      if (++P > P_MAX) {
        fclose(file_log);
        char str[50];
        sprintf(str, "over %d inversions", P_MAX);
        wrong_answer(str);
      }
      state[-pos] = !state[-pos];
      pos = state[-pos] ? IX[-(1 + pos)] : IY[-(1 + pos)];
    } else {
      if (pos == 0) {
        break;
      }
      if (k >= ___N) {
        fclose(file_log);
        wrong_answer("wrong motion 1");
      }
      if (pos != ___A[k++]) {
        fclose(file_log);
        wrong_answer("wrong motion 2");
      }
      pos = IC[pos];
    }
  }
  fclose(file_log);
  if (k != ___N) {
    wrong_answer("wrong motion 3");
  }
  for (int j = 1; j <= S; ++j) {
    if (state[j]) {
      wrong_answer("state 'Y'");
    }
  }
  printf("Accepted: %d %d\n", S, P);
}

}  // namespace

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y) {
  if (answered) {
    wrong_answer("answered not exactly once");
  }
  answered = true;
  // check if input format is correct
  if ((int)C.size() != ___M + 1) {
    wrong_answer("wrong array length");
  }
  if (X.size() != Y.size()) {
    wrong_answer("wrong array length");
  }
  S = X.size();
  IC = C;
  IX = X;
  IY = Y;
}

int main() {
    file("doll");
  ___M = read_int();
  ___N = read_int();
  ___A.resize(___N);
  for (int k = 0; k < ___N; ++k) {
    ___A[k] = read_int();
  }

  answered = false;
  create_circuit(___M, ___A);
  if (!answered) {
    wrong_answer("answered not exactly once");
  }
  FILE *file_out = fopen("out.txt", "w");
  fprintf(file_out, "%d\n", S);
  for (int i = 0; i <= ___M; ++i) {
    fprintf(file_out, "%d\n", IC[i]);
  }
  for (int j = 1; j <= S; ++j) {
    fprintf(file_out, "%d %d\n", IX[j - 1], IY[j - 1]);
  }
  fclose(file_out);
  simulate();
  return 0;
}
#endif

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 27 ms 4900 KB Output is correct
3 Correct 25 ms 4852 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 48 ms 6804 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 27 ms 4900 KB Output is correct
3 Correct 25 ms 4852 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 48 ms 6804 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 52 ms 7576 KB Output is correct
9 Correct 54 ms 8044 KB Output is correct
10 Correct 77 ms 11208 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 27 ms 4900 KB Output is correct
3 Correct 25 ms 4852 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 48 ms 6804 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 52 ms 7576 KB Output is correct
9 Correct 54 ms 8044 KB Output is correct
10 Correct 77 ms 11208 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 76 ms 10684 KB Output is correct
15 Correct 49 ms 7092 KB Output is correct
16 Correct 72 ms 10392 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 77 ms 10844 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 45 ms 6076 KB Output is correct
3 Correct 47 ms 6104 KB Output is correct
4 Correct 72 ms 8860 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 45 ms 6076 KB Output is correct
3 Correct 47 ms 6104 KB Output is correct
4 Correct 72 ms 8860 KB Output is correct
5 Correct 73 ms 10308 KB Output is correct
6 Correct 72 ms 10040 KB Output is correct
7 Correct 71 ms 10132 KB Output is correct
8 Correct 70 ms 9760 KB Output is correct
9 Correct 46 ms 6128 KB Output is correct
10 Correct 70 ms 9708 KB Output is correct
11 Correct 69 ms 9388 KB Output is correct
12 Correct 46 ms 6376 KB Output is correct
13 Correct 54 ms 6768 KB Output is correct
14 Correct 48 ms 6848 KB Output is correct
15 Correct 50 ms 6892 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 41 ms 6728 KB Output is correct
18 Correct 48 ms 6332 KB Output is correct
19 Correct 56 ms 6252 KB Output is correct
20 Correct 70 ms 9592 KB Output is correct
21 Correct 70 ms 9292 KB Output is correct
22 Correct 74 ms 9308 KB Output is correct