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"
#warning That's not FB, that's my FB
using namespace std;
int n,m;
vector<int> a;
vector<vector<int>> pos;
vector<int> unde;
int cur = 1;
vector<int> c, x, y;
int ngl, kgl, pgl;
void build(int nume, int l, int r)
{
int mij = (l + r) / 2;
if (mij <= pgl)
x[-nume - 1] = c[ngl];
else
{
if (l != mij)
{
x[-nume - 1] = -cur;
cur++;
x.push_back(0);
y.push_back(0);
build(x[-nume - 1], l, mij);
}
else
{
//int pz = pos[ngl][unde[ngl]] + 1;
//unde[ngl]++;
x[-nume - 1] = 3 * n;
}
}
if (mij + 1 != r)
{
y[-nume - 1] = -cur;
cur++;
x.push_back(0);
y.push_back(0);
build(y[-nume - 1], mij + 1, r);
}
else
{
//int pz = pos[ngl][unde[ngl]] + 1;
//unde[ngl]++;
y[-nume - 1] = 3 * n;
}
}
void build_sgt(int nod)
{
c[nod] = -cur;
cur++;
x.push_back(0);
y.push_back(0);
ngl = nod;
kgl = __lg(pos[nod].size());
if ((1 << kgl) < pos[nod].size())
kgl++;
pgl = (1 << kgl) - (int)pos[nod].size();
build(c[nod], 1, (1 << kgl));
}
int cr = 0;
vector<int> how;
void gogo(int nod)
{
//cout << nod << endl;
if (nod == 0)
return;
if (nod >= 1)
{
if (nod == a[cr])
cr++;
gogo(c[nod]);
return;
}
//cout << x[-nod - 1] << ' ' << y[-nod - 1] << ' ' << how[-nod - 1] << endl;
if (how[-nod - 1] == 0)
{
how[-nod - 1] = 1;
if (x[-nod - 1] > 2 * n)
{
x[-nod - 1] = a[cr];
cr++;
}
gogo(x[-nod - 1]);
}
else
{
how[-nod - 1] = 0;
if (y[-nod - 1] > 2 * n)
{
y[-nod - 1] = a[cr];
cr++;
}
gogo(y[-nod - 1]);
}
}
void create_circuit(int M, vector<int> A)
{
n = A.size();
a = A;
m = M;
pos.resize(m + 1);
unde.resize(m + 1);
for (int i = 0; i < a.size(); i++)
pos[a[i]].push_back(i);
a.push_back(0);
c.resize(m + 1);
c[0] = a[0];
for (int i = 1; i <= m; i++)
{
if (pos[i].empty())
c[i] = 0;
else if (pos[i].size() == 1)
c[i] = a[pos[i][0] + 1];
else
build_sgt(i);
}
/*for (auto it : c)
cout << it << ' ';
cout << endl;
for (auto it : x)
cout << it << ' ';
cout << endl;
for (auto it : y)
cout << it << ' ';
cout << endl;*/
how.resize(cur);
gogo(a[0]);
answer(c, x, y);
}
Compilation message (stderr)
doll.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
3 | #warning That's not FB, that's my FB
| ^~~~~~~
doll.cpp: In function 'void build_sgt(int)':
doll.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if ((1 << kgl) < pos[nod].size())
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for (int i = 0; i < a.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... |