Submission #1191242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191242		MatteoArcari	Mechanical Doll (IOI18_doll)	C++20	53 / 100	130 ms	43796 KiB

doll

#include <bits/stdc++.h>
using namespace std;

void answer(vector<int> c, vector<int> x, vector<int> y);

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;

    void wrong_answer(const char *MSG) {
      exit(1);
    }
    
    void simulate() {
      if (S > S_MAX) {
        char str[50];
        exit(0);
      }
      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;
      for (;;) {
        if (pos < 0) {
          if (++P > P_MAX) {
            char str[50];
            exit(0);
          }
          state[-pos] = !state[-pos];
          pos = state[-pos] ? IX[-(1 + pos)] : IY[-(1 + pos)];
        } else {
          if (pos == 0) {
            break;
          }
          if (k >= N) {
            wrong_answer("wrong motion");
          }
          if (pos != A[k++]) {
            wrong_answer("wrong motion");
          }
          pos = IC[pos];
        }
      }
      if (k != N) {
        wrong_answer("wrong motion");
      }
      for (int j = 1; j <= S; ++j) {
        if (state[j]) {
            exit(0);
        }
      }
    }
    
}  // 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 C");
    }
    if (X.size() != Y.size()) {
    wrong_answer("wrong array length XY");
    }
    S = X.size();
    IC = C;
    IX = X;
    IY = Y;
}

void create_circuit(int m, vector<int> a) {
    int n = a.size();
    A = a; N = n; M = m;
    vector<int> c(m + 1), x, y;
    vector<vector<int>> cnt(m + 1);
    cnt[0].push_back(a[0]);
    a.push_back(0);
    for (int i = 0; i < n; i++) {
        cnt[a[i]].push_back(a[i + 1]);
    }

    c[0] = a[0];

    queue<int> s;
    vector<vector<int>> to;

    for (int i = 1; i <= m; i++) {
        if (cnt[i].size() == 0) {
            c[i] = 0;
            continue;
        }
        if (cnt[i].size() == 1) {
            c[i] = cnt[i][0];
            continue;
        }
        int j = x.size() + 1;
        c[i] = -j;
        s.push(j);
        x.push_back(-j);
        y.push_back(-j);
        to.push_back(cnt[i]);
    }

    while (!s.empty()) {
        int j = s.front();
        s.pop();

        if (to[j - 1].size() == 2) {
            x[j - 1] = to[j - 1][0];
            y[j - 1] = to[j - 1][1];
            continue;
        }

        vector<int> _a, _b;
        for (int i = 0; i < to[j - 1].size(); i++) {
            if (i & 1) _b.push_back(to[j - 1][i]);
            else _a.push_back(to[j - 1][i]);
        }

        if (_a.size() > _b.size()) {
            _b.push_back(_a.back());
            _a.pop_back();
            _a.push_back(-j);
        }

        int k = x.size() + 1;
        x[j - 1] = -k;
        x.push_back(-k);
        y.push_back(-k);
        to.push_back(_a);
        s.push(k);

        k++;
        y[j - 1] = -k;
        x.push_back(-k);
        y.push_back(-k);
        to.push_back(_b);
        s.push(k);
    }

    _answer(c, x, y);
    simulate();
    answer(c, x, y);
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56