Submission #1032857

#TimeUsernameProblemLanguageResultExecution timeMemory
1032857parsadox2Mechanical Doll (IOI18_doll)C++17
65.67 / 100
105 ms18448 KiB
#include <bits/stdc++.h> #include "doll.h" using namespace std; const int N = 2e5 + 10; int n , m; vector <int> C , X , Y , adj[N]; int Rev(int x , int cnt) { int res = 0; for(int i = 0 ; i < cnt ; i++) if((x >> i) & 1) res |= (1 << (cnt - i - 1)); return res; } int Solve(vector <int> vec , bool flg = true) { if(vec.size() == 1) return vec[0]; X.push_back(0); Y.push_back(0); int now = X.size(); vector <int> v[2]; if(flg) { int tmp = 1 , cnt = 0; while(tmp < vec.size()) { tmp *= 2; cnt++; } vector <int> fake(tmp , 0); for(int i = 0 ; i < tmp - vec.size() ; i++) fake[Rev(i , cnt)] = -now; int pos = 0; for(int i = 0 ; i < tmp ; i++) if(fake[i] != -now) { fake[i] = vec[pos]; pos++; } vec = fake; } /*cout << "SOLVE " << endl; for(auto u : vec) cout << u << " "; cout << endl;*/ if(vec[0] < 0 && vec.back() < 0) { X[now - 1] = vec[0]; Y[now - 1] = vec[0]; return -now; } for(int i = 0 ; i < vec.size() ; i++) v[i % 2].push_back(vec[i]); int tmp = Solve(v[0] , 0); X[now - 1] = tmp; tmp = Solve(v[1] , 0); Y[now - 1] = tmp; return -1 * now; } void Build(int v) { if(adj[v].empty()) { C[v] = 0; return; } int tmp = Solve(adj[v]); C[v] = tmp; } void create_circuit(int mm , vector <int> A) { n = A.size(); m = mm; C.resize(m + 1); adj[0].push_back(A[0]); for(int i = 0 ; i + 1 < n ; i++) adj[A[i]].push_back(A[i + 1]); adj[A.back()].push_back(0); for(int i = 0 ; i <= m ; i++) { Build(i); } /*for(int i = 0 ; i <= m ; i++) cout << i << " -> " << C[i] << endl; for(int i = 0 ; i < X.size() ; i++) cout << -(i + 1) << " : " << X[i] << " " << Y[i] << endl;*/ answer(C , X , Y); }

Compilation message (stderr)

doll.cpp: In function 'int Solve(std::vector<int>, bool)':
doll.cpp:29:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   while(tmp < vec.size())
      |         ~~~~^~~~~~~~~~~~
doll.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i = 0 ; i < tmp - vec.size() ; i++)
      |                   ~~^~~~~~~~~~~~~~~~~~
doll.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i = 0 ; i < vec.size() ; i++)
      |                  ~~^~~~~~~~~~~~
#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...