Submission #1068396

#TimeUsernameProblemLanguageResultExecution timeMemory
1068396TheQuantiXMechanical Doll (IOI18_doll)C++17
37 / 100
139 ms10816 KiB
#include <bits/stdc++.h> #include "doll.h" using namespace std; using ll = long long; constexpr ll INF = 1000000000; ll conn; set<ll> st; ll nxt = -2; void connect(ll x, vector<int> &X, vector<int> &Y, ll idx) { // cout << x << '\n'; if (X[idx] == 0) { X[idx] = x; } else { Y[idx] = x; } } void distribute(ll sz, vector<int> &X, vector<int> &Y, vector<int> &A, ll idx) { // cout << idx << ' ' << sz << ' ' << ex << endl; if (idx >= X.size()) { X.resize(idx + 1); } if (idx >= Y.size()) { Y.resize(idx + 1); } // cout << sz << ' ' << e << '\n'; X[idx] = 0; Y[idx] = 0; if (sz == 2) { connect(INF, X, Y, idx); connect(INF, X, Y, idx); return; } X[idx] = nxt; nxt--; Y[idx] = nxt; nxt--; distribute(sz - sz / 2, X, Y, A, -X[idx] - 1); distribute(sz / 2, X, Y, A, -Y[idx] - 1); } void create_circuit(int M, vector<int> A) { ll NN = A.size(); A.push_back(-1); ll N = A.size(); ll y = 0; ll ex = 1; while (ex < N) { ex *= 2; } while (A.size() < ex) { A.push_back(-1); } N = A.size(); A[N - 1] = 0; vector<int> C, X, Y; C.push_back(-1); for (int i = 0; i < M; i++) { C.push_back(-1); } distribute(N, X, Y, A, 0); // for (int i = 0; i < C.size(); i++) { // cout << C[i] << '\n'; // } // cout << conn << '\n'; while (!st.empty()) { ll x = *st.begin(); st.erase(x); Y[conn] = -x - 1; conn = x; } ll pos = 0, cnt = 0; vector<bool> state(X.size()); // for (int i = 0; i < X.size(); i++) { // cout << X[i] << ' ' << Y[i] << endl; // } do { // cout << pos << endl; if (pos >= 0) { pos = C[pos]; } else { // cout << '\t' << state[-pos - 1] << endl; if (state[-pos - 1] == 0) { if (X[-pos - 1] == INF) { X[-pos - 1] = A[cnt++]; } state[-pos - 1] = !state[-pos - 1]; pos = X[-pos - 1]; } else { if (Y[-pos - 1] == INF) { Y[-pos - 1] = A[cnt++]; } state[-pos - 1] = !state[-pos - 1]; pos = Y[-pos - 1]; } } } while (pos != 0); // for (int i = 0; i < X.size(); i++) { // cout << '\t' << X[i] << ' ' << Y[i] << endl; // } assert(X.size() <= NN * 2); answer(C, X, Y); }

Compilation message (stderr)

doll.cpp: In function 'void distribute(ll, std::vector<int>&, std::vector<int>&, std::vector<int>&, ll)':
doll.cpp:25:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     if (idx >= X.size()) {
      |         ~~~~^~~~~~~~~~~
doll.cpp:28:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if (idx >= Y.size()) {
      |         ~~~~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:56:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   56 |     while (A.size() < ex) {
      |            ~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from doll.cpp:1:
doll.cpp:108:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  108 |     assert(X.size() <= NN * 2);
      |            ~~~~~~~~~^~~~~~~~~
doll.cpp:51:8: warning: unused variable 'y' [-Wunused-variable]
   51 |     ll y = 0;
      |        ^
#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...