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;
int S;
vector<int> X, Y;
vector<int> newv;
int make_switch(int st, int dr, int idd = -1)
{
if(st == dr) return newv[st];
if(st + 1 == dr)
{
if(idd == -1)
{
S++;
X.push_back(newv[st]);
Y.push_back(newv[dr]);
return -S;
}
else
{
X[idd - 1] = newv[st];
Y[idd - 1] = newv[dr];
return -idd;
}
}
int id = -1;
if(idd == -1)
{
S++;
id = S;
X.push_back(0);
Y.push_back(0);
}
else
id = idd;
int mij = st + (dr - st) / 2;
int sl = make_switch(st, mij);
int sr = make_switch(mij + 1, dr);
X[id - 1] = sl;
Y[id - 1] = sr;
return -id;
}
int make_switch(vector<int> v)
{
if(v.empty()) return 0;
if(v.size() == 1)
return v[0];
S++;
X.push_back(0);
Y.push_back(0);
int l = v.size();
int lst = v.back();
v.pop_back();
while( (l & (l - 1)) != 0 )
{
v.push_back(-S);
l++;
}
v.push_back(lst);
newv.clear();
newv.resize(v.size());
int lg = 0;
for(lg = 0; (1 << lg) < v.size(); lg++);
for(int i = 0; i < v.size(); i++)
{
int msk = i;
int rmsk = 0;
for(int j = 0; j < lg; j++)
if((msk >> j) & 1)
rmsk |= (1 << (lg - j - 1));
newv[rmsk] = v[i];
}
return make_switch(0, l - 1, S);
}
void create_circuit(int M, vector<int> A)
{
vector< vector<int> > v;
v.resize(M + 2);
int lst = 0;
for(int i = 0; i < A.size(); i++)
{
v[lst].push_back(A[i]);
lst = A[i];
}
v[lst].push_back(0);
vector<int> ex;
ex.resize(M + 1);
X.clear(), Y.clear();
S = 0;
for(int i = 0; i <= M; i++)
{
int l = v[i].size();
ex[i] = make_switch(v[i]);
}
answer(ex, X, Y);
}
Compilation message (stderr)
doll.cpp: In function 'int make_switch(std::vector<int>)':
doll.cpp:74:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(lg = 0; (1 << lg) < v.size(); lg++);
| ~~~~~~~~~~^~~~~~~~~~
doll.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i = 0; i < A.size(); i++)
| ~~^~~~~~~~~~
doll.cpp:107:13: warning: unused variable 'l' [-Wunused-variable]
107 | int l = v[i].size();
| ^
# | 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... |