oj.uz

Submission #250948

# Submission time Handle Problem Language Result Execution time Memory
250948 2020-07-19T14:23:20 Z fedoseevtimofey Mechanical Doll (IOI18_doll) C++14
100 / 100
 166 ms 14760 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
 
using namespace std;
 
typedef long long ll;
 
#include "doll.h"
 
void create_circuit(int m, vector <int> a) {
  int n = a.size();
  vector <vector <int>> where(m + 1);
  for (int i = 0; i < n; ++i) {
    where[a[i]].push_back(i);
  }
  a.push_back(0);
  int uk = 0;
  vector <int> c(m + 1);
  c[0] = a[0];
  vector <int> x, y;
  auto new_node = [&] () {
    x.push_back(-1);
    y.push_back(-1);
    return uk++;
  };
 
  int lg = 1;
 
  while ((1 << lg) <= n) ++lg;
 
  const int Inf = 1e9;
 
  int root = new_node();
  for (int v = 1; v <= m; ++v) {
    if (!where[v].empty()) {
      c[v] = -(root + 1);
    }
  }
  //cout << "gogo " << v << endl;
  function <void(int, int, int, int)> rec = [&] (int u, int lvl, int num, int skip) {
    int sz = (1 << (lvl - 1));
    int skip_l = min(sz, skip);
    int skip_r = skip - skip_l;
    int num_r = num | (1 << (lg - lvl));
    int num_l = num;
    if (skip_l == sz) {
      x[u] = root + 1;
    } else if (sz > 1) {
      x[u] = new_node() + 1;
      rec(x[u] - 1, lvl - 1, num_l, skip_l);
    } else {
      assert(sz == 1);
      x[u] = Inf + num_l; 
    }
    assert(skip_r < sz);
    if (sz > 1) {
      y[u] = new_node() + 1;
      rec(y[u] - 1, lvl - 1, num_r, skip_r);
    } else {
      y[u] = Inf + num_r;
    }
  };
 
  rec(root, lg, 0, (1 << lg) - n);
 
  vector <pair <int, int>> cur;
  for (int u = root; u < uk; ++u) {
    if (x[u] >= Inf) {
      cur.push_back({x[u], -u});
    }
    if (y[u] >= Inf) {
      cur.push_back({y[u], u});
    }
  }
 
  sort(cur.begin(), cur.end());
  for (int i = 0; i < (int)cur.size(); ++i) {
    if (cur[i].second < 0) {
      x[-cur[i].second] = -a[i + 1];
    } else {
      y[cur[i].second] = -a[i + 1];
    }
  }
  for (int i = 0; i < (int)x.size(); ++i) {
    if (x[i] <= 0) {
      x[i] *= -1;
    } else {
      x[i] *= -1;
    }
  }
  for (int i = 0; i < (int)y.size(); ++i) {
    if (y[i] <= 0) {
      y[i] *= -1;
    } else {
      y[i] *= -1;
    }
  }
  /*for (int i = 0; i <= m; ++i) {
    cout << c[i] << '\n';
  }
  cout << "done\n";
  for (int i = 0; i < (int)x.size(); ++i) {
    cout << x[i] << ' ' << y[i] << endl;
  }*/
  answer(c, x, y);
}
 
#ifdef LOCAL
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;
  cin >> x;
  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");
      }
      if (pos != A[k++]) {
        fclose(file_log);
        wrong_answer("wrong motion");
      }
      pos = IC[pos];
    }
  }
  fclose(file_log);
  if (k != N) {
    wrong_answer("wrong motion");
  }
  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() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  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 2 ms 204 KB Output is correct
2 Correct 63 ms 8520 KB Output is correct
3 Correct 73 ms 7452 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 19 ms 3792 KB Output is correct
6 Correct 77 ms 10960 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 2 ms 204 KB Output is correct
2 Correct 63 ms 8520 KB Output is correct
3 Correct 73 ms 7452 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 19 ms 3792 KB Output is correct
6 Correct 77 ms 10960 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 88 ms 9764 KB Output is correct
9 Correct 113 ms 11692 KB Output is correct
10 Correct 166 ms 14760 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 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 2 ms 204 KB Output is correct
2 Correct 63 ms 8520 KB Output is correct
3 Correct 73 ms 7452 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 19 ms 3792 KB Output is correct
6 Correct 77 ms 10960 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 88 ms 9764 KB Output is correct
9 Correct 113 ms 11692 KB Output is correct
10 Correct 166 ms 14760 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 135 ms 12480 KB Output is correct
15 Correct 84 ms 7616 KB Output is correct
16 Correct 121 ms 11400 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 152 ms 13340 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 1 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 61 ms 6180 KB Output is correct
3 Correct 61 ms 5852 KB Output is correct
4 Correct 100 ms 8812 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 61 ms 6180 KB Output is correct
3 Correct 61 ms 5852 KB Output is correct
4 Correct 100 ms 8812 KB Output is correct
5 Correct 133 ms 11744 KB Output is correct
6 Correct 117 ms 10908 KB Output is correct
7 Correct 118 ms 11128 KB Output is correct
8 Correct 120 ms 10392 KB Output is correct
9 Correct 60 ms 5896 KB Output is correct
10 Correct 104 ms 9620 KB Output is correct
11 Correct 102 ms 10160 KB Output is correct
12 Correct 63 ms 7072 KB Output is correct
13 Correct 72 ms 7488 KB Output is correct
14 Correct 88 ms 7472 KB Output is correct
15 Correct 83 ms 7796 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 67 ms 6696 KB Output is correct
18 Correct 64 ms 6680 KB Output is correct
19 Correct 64 ms 6436 KB Output is correct
20 Correct 105 ms 9440 KB Output is correct
21 Correct 99 ms 9576 KB Output is correct
22 Correct 97 ms 9252 KB Output is correct