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 "doll.h"
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 500010
using namespace std;
int n, m, k, logg;
vector<int> a, X, Y;
int which[MAXN];
int s=-1;
map<int, int> lc, rc;
ll two[30];
vector<int> all;
void solve(int sw, int l, int r, int cnt)
{
if ((r-l)==1)
{
if (cnt>=1)
rc[sw]=which[r];
else
rc[sw]=-1;
if (cnt==2)
lc[sw]=which[l];
else
lc[sw]=-1;
return;
}
if ((r-l+1)/2>=cnt)
{
lc[sw]=-1;
rc[sw]=--s;
int mid=l+(r-l)/2;
solve(rc[sw], mid+1, r, cnt);
}
else if (cnt>(r-l+1)/2)
{
lc[sw]=--s;
rc[sw]=--s;
int mid=l+(r-l)/2;
solve(lc[sw], l, mid, cnt-(mid-l+1));
solve(rc[sw], mid+1, r, (mid-l+1));
}
}
void findorder()
{
two[0]=1;
for (int i=1; i<=20; i++) two[i]=(two[i-1]*2);
for (int i=0; i<k; i++) {
int step = 0; int ii=i;
int ress=0;
while (i) {
int cif = i % 2;
i /= 2;
ress = ress + cif * two[logg - 1 - step];
step++;
}
i=ii;
all.pb(ress+1);
}
//for (int i=0; i<all.size(); i++) cout<<all[i]<<" ";
//cout<<endl;
int j=0;
for (int i=0; i<all.size(); i++)
{
if (all[i]>(k-n)) { /*cout<<all[i]<<" "<<a[j]<<endl;*/ which[all[i]]=a[j++]; }
}
}
void create_circuit(int M, std::vector<int> A) {
for (int i=0; i<A.size(); i++) a.pb(A[i]);
a.pb(0);
m=M; n = a.size();
k=1; logg=0;
while (k<n) { k*=2; logg++; }
vector<int> C(m+1);
for (int i=0; i<=m; i++) C[i]=-1;
findorder();
solve(s, 1, k, n);
for (int i=-1; i>=s; i--)
{
X.pb(lc[i]);
Y.pb(rc[i]);
}
answer(C, X, Y);
}
/*
5 5
1 3 1 4 1
*/
Compilation message (stderr)
doll.cpp: In function 'void findorder()':
doll.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i=0; i<all.size(); i++)
| ~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i=0; i<A.size(); i++) a.pb(A[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... |