제출 #413078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413078		usachevd0	자동 인형 (IOI18_doll)	C++14	컴파일 에러	0 ms	0 KiB

doll

#include <bits/stdc++.h>
#ifndef LOCAL
    #include "seats.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}

const int INF32 = 1e9;
const int maxN = 4e5;
int X[maxN], Y[maxN];
int st[maxN];
int ord[maxN], pos[maxN];

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
void create_circuit(int m, vector<int> a) {
    int n = a.size();
    a.push_back(0);
    int S = 0;
    auto newSwitch = [&]() -> int {
        ++S;
        return -S;
    };
    
    vector<int> b(n + 1);
    iota(all(b), 0);
    while (b.size() > 1) {
        if (b.size() & 1) {
            int last = b.back();
            b.pop_back();
            b.push_back(INF32);
            b.push_back(last);
        }
        vector<int> new_b;
        for (int i = 0; i < b.size(); i += 2) {
            int s = newSwitch();
            int sid = -s - 1;
            X[sid] = b[i];
            Y[sid] = b[i + 1];
            new_b.push_back(s);
        }
        swap(b, new_b);
    }
    int root = b[0];
    for (int s = 0; s < S; ++s) {
        if (X[s] == INF32) X[s] = root;
        if (Y[s] == INF32) Y[s] = root;
    }
    
    int vis = 0;
    int v = root;
    while (vis < n + 1) {
        if (v < 0) {
            int sid = -v - 1;
            if (!st[sid]) {
                v = X[sid];
            } else {
                v = Y[sid];
            }
            st[sid] ^= 1;
        } else {
            pos[v] = vis;
            ++vis;
            v = root;
        }
    }
    // mdebug(pos, m + 1);
    // mdebug(X, S);
    // mdebug(Y, S);
    for (int s = 0; s < S; ++s) {
        if (X[s] >= 0) {
            X[s] = a[pos[X[s]]];
        }
        if (Y[s] >= 0) {
            Y[s] = a[pos[Y[s]]];
        }
    }
    vector<int> x(S), y(S);
    for (int i = 0; i < S; ++i) {
        x[i] = X[i];
        y[i] = Y[i];
    }
    // debug(root);
    // debug(x);
    // debug(y);
    answer(vector<int>(m + 1, root), x, y);
}



#ifdef LOCAL

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");
      }
      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);
}

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("in", "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;
}


// int32_t main() {
// #ifdef LOCAL
//     freopen("in", "r", stdin);
// #endif
//     ios::sync_with_stdio(0);
//     cin.tie(0);
    
    

//     return 0;
// }
#endif

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp:3:14: fatal error: seats.h: No such file or directory
    3 |     #include "seats.h"
      |              ^~~~~~~~~
compilation terminated.