Submission #568062

#TimeUsernameProblemLanguageResultExecution timeMemory
568062hoanghq2004Mechanical Doll (IOI18_doll)C++14
37 / 100
140 ms13204 KiB
#include <bits/stdc++.h> #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include "doll.h" using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>; //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); //// cout << 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; //} const int Nm = 4e5 + 10; int cnt; int x[Nm], y[Nm]; int build(vector <int> s) { if (s.size() == 1) return - s[0]; vector <int> lft, rgt; int cur = ++cnt; for (int i = 0; i < s.size() - s.size() % 2; ++i) if (i & 1) rgt.push_back(s[i]); else lft.push_back(s[i]); if (s.size() % 2) { lft.push_back(- cnt); rgt.push_back(s.back()); } x[cur] = build(lft); y[cur] = build(rgt); return cur; } void create_circuit(int M, std::vector<int> A) { vector<int> C(M + 1); A.push_back(0); int N = A.size(); C[0] = - build(A); for (int i = 1; i <= M; ++i) C[i] = -1; vector <int> X, Y; for (int i = 1; i <= cnt; ++i) X.push_back(- x[i]), Y.push_back(- y[i]); // cout << X.size() << ' ' << Y.size() << '\n'; answer(C, X, Y); } // //int main() { //// freopen("test.inp", "r", stdin); // 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; //}

Compilation message (stderr)

doll.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
doll.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
doll.cpp: In function 'int build(std::vector<int>)':
doll.cpp:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for (int i = 0; i < s.size() - s.size() % 2; ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:149:9: warning: unused variable 'N' [-Wunused-variable]
  149 |     int N = A.size();
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...