This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |