oj.uz

Submission #837745

# Submission time Handle Problem Language Result Execution time Memory
837745 2023-08-25T15:24:09 Z becaido Mechanical Doll (IOI18_doll) C++17
100 / 100
 88 ms 10596 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "doll.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() { cout << "\n"; }
template<typename T, typename...U>
void dout(T t, U...u) { cout << t << (sizeof...(u) ? ", " : ""), dout(u...); }
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#ifdef WAIMAI
void answer(vector<int> C, vector<int> X, vector<int> Y);
#endif

void create_circuit(int M, vector<int> A) {
    int N;
    vector<int> C, X, Y;
    A.pb(0);
    N = A.size();
    C.resize(M + 1, -1);

    int cur = 0;
    auto divide = [&](auto divide, int sz, int dep)->int {
        cur++;
        int pos = -cur, i = -(pos + 1);
        X.pb(-1), Y.pb(-1);
        if (dep == 0) {
            if (sz == 1) Y[i] = 0;
            if (sz == 2) X[i] = Y[i] = 0;
            return pos;
        }
        int half = 1 << dep;
        if (sz <= half) Y[i] = divide(divide, sz, dep - 1);
        else {
            X[i] = divide(divide, sz - half, dep - 1);
            Y[i] = divide(divide, half, dep - 1);
        }
        return pos;
    };
    divide(divide, N, __lg(N - 1));

    vector<int> state(cur, 0);
    int p = 0, pos = -1;
    while (p < N) {
        int i = -(pos + 1);
        if (state[i] == 0) {
            if (X[i] == 0) X[i] = A[p++], pos = -1;
            else pos = X[i];
        } else {
            if (Y[i] == 0) Y[i] = A[p++], pos = -1;
            else pos = Y[i];
        }
        state[i] ^= 1;
    }
    answer(C, X, Y);
}

/*
in1
4 4
1 2 1 3
out1
*/

#ifdef WAIMAI
namespace {

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

int M, N;
vector<int> A;

bool answered;
int S;
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;
  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(vector<int> C, vector<int> X, 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() {
  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 31 ms 4432 KB Output is correct
3 Correct 28 ms 4544 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 44 ms 6580 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 31 ms 4432 KB Output is correct
3 Correct 28 ms 4544 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 44 ms 6580 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 56 ms 6952 KB Output is correct
9 Correct 58 ms 7372 KB Output is correct
10 Correct 86 ms 10596 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 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 31 ms 4432 KB Output is correct
3 Correct 28 ms 4544 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 44 ms 6580 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 56 ms 6952 KB Output is correct
9 Correct 58 ms 7372 KB Output is correct
10 Correct 86 ms 10596 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 84 ms 9988 KB Output is correct
15 Correct 54 ms 6412 KB Output is correct
16 Correct 83 ms 9804 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 88 ms 10244 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 0 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 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 49 ms 5832 KB Output is correct
3 Correct 49 ms 5748 KB Output is correct
4 Correct 78 ms 8764 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 49 ms 5832 KB Output is correct
3 Correct 49 ms 5748 KB Output is correct
4 Correct 78 ms 8764 KB Output is correct
5 Correct 82 ms 9564 KB Output is correct
6 Correct 83 ms 9296 KB Output is correct
7 Correct 84 ms 9564 KB Output is correct
8 Correct 79 ms 9132 KB Output is correct
9 Correct 50 ms 5744 KB Output is correct
10 Correct 79 ms 8944 KB Output is correct
11 Correct 77 ms 8764 KB Output is correct
12 Correct 51 ms 5748 KB Output is correct
13 Correct 57 ms 6164 KB Output is correct
14 Correct 53 ms 6216 KB Output is correct
15 Correct 54 ms 6288 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 49 ms 7092 KB Output is correct
18 Correct 50 ms 5748 KB Output is correct
19 Correct 50 ms 5740 KB Output is correct
20 Correct 78 ms 8844 KB Output is correct
21 Correct 75 ms 8708 KB Output is correct
22 Correct 78 ms 8764 KB Output is correct