Submission #432654

#TimeUsernameProblemLanguageResultExecution timeMemory
432654frodakcinMechanical Doll (IOI18_doll)C++11
12 / 100
97 ms9344 KiB
#include "doll.h" #include <cstdio> #include <cassert> #include <vector> #include <algorithm> const int MN = 2e5; int S; std::vector<int> X, Y; bool root[MN], state[MN]; int dfs(int l, int r, int ql) { int n=++S; X.push_back(1), Y.push_back(1); if(r-l>2) { int m=l+(r-l)/2; if(ql < m) X[n-1] = dfs(l, m, ql); Y[n-1] = dfs(m, r, ql); } else root[n]=1; return n; } void create_circuit(int M, std::vector<int> A) { X.reserve(MN); Y.reserve(MN); int N = A.size(); std::vector<int> C(M + 1); C[0]=A[0]; if(N==1) { C[C[0]]=0; answer(C, X, Y); return; } for(int i=1;i<=M;++i) C[i]=-1; //for(auto x:A) printf("%d ", x); printf("\n"); std::rotate(A.begin(), A.begin()+1, A.end()); A.back()=0; if(A.size()&1) A.insert(A.begin(), -1); //for(auto x:A) printf("%d ", x); printf("\n"); int d = 31 - __builtin_clz((int)A.size()-1); assert((1<<d+1) >= A.size() && A.size() > (1<<d)); int top; top = dfs(0, 1<<d+1, (1<<d+1)-A.size()); for(int& x:X) x*=-1; for(int& x:Y) x*=-1; int ctr=0; int n=-top; for(;n != 0;) { //printf("ideal: %d\n", n); if(n > 0) n = -top; else if(root[-n]) { state[-n] ^= 1; assert(ctr < A.size()); n = (state[-n] ? X[-n-1] : Y[-n-1]) = A[ctr++]; } else { state[-n] ^= 1; n = state[-n] ? X[-n-1] : Y[-n-1]; } } //printf("%d %lu\n", ctr, A.size()); assert(ctr == A.size()); answer(C, X, Y); }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from doll.cpp:3:
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:52:14: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   52 |  assert((1<<d+1) >= A.size() && A.size() > (1<<d));
      |             ~^~
doll.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  assert((1<<d+1) >= A.size() && A.size() > (1<<d));
      |         ~~~~~~~~~^~~~~~~~~~~
doll.cpp:52:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |  assert((1<<d+1) >= A.size() && A.size() > (1<<d));
      |                                 ~~~~~~~~~^~~~~~~~
doll.cpp:55:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   55 |  top = dfs(0, 1<<d+1, (1<<d+1)-A.size());
      |                  ~^~
doll.cpp:55:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   55 |  top = dfs(0, 1<<d+1, (1<<d+1)-A.size());
      |                           ~^~
In file included from /usr/include/c++/10/cassert:44,
                 from doll.cpp:3:
doll.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    assert(ctr < A.size());
      |           ~~~~^~~~~~~~~~
doll.cpp:79:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  assert(ctr == 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...