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<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x<<endl
struct parent
{
int p;
short edge;
};
vector<int> X;
vector<int> Y;
map<int,parent> memo;
int NEXT_FREE_INDEX=1;
int limit;
void createTree(int i,int lv,int sum,int unused)
{
if(lv==limit-1){ //Last level of switches
if(unused==1)
X.push_back(-1);
else{
X.push_back(sum);
parent x={i,0};
memo[sum]=x;
}
sum+=(1<<lv);
parent x={i,1};
Y.push_back(sum);
memo[sum]=x;
}
else{
int child_size=(1<<(limit-lv-1));
if(unused>=child_size){ //Drop left child
X.push_back(-1);
Y.push_back(-NEXT_FREE_INDEX);
NEXT_FREE_INDEX++;
createTree(NEXT_FREE_INDEX-1,lv+1,sum+(1<<lv),unused-child_size);
}
else{
X.push_back(-NEXT_FREE_INDEX);
NEXT_FREE_INDEX++;
Y.push_back(0);
createTree(NEXT_FREE_INDEX-1,lv+1,sum,unused);
Y[i-1]=-NEXT_FREE_INDEX;
NEXT_FREE_INDEX++;
createTree(NEXT_FREE_INDEX-1,lv+1,sum+(1<<lv),0);
}
}
}
void create_circuit(int m, vector<int> A) {
A.push_back(0);
int n=A.size();
vector<int> C(m+1);
for(int i=0;i<=m;i++){
C[i]=-1;
}
int LOG=0;
while((1<<LOG)<n){
LOG++;
}
NEXT_FREE_INDEX++;
limit=LOG;
createTree(1,0,0,(1<<LOG)-n);
/*for(int i=0;i<n;i++){
cout<<X[i]<<" "<<Y[i]<<endl;
}*/
int j=0;
map<int,parent>::iterator it;
for(it=memo.begin();it!=memo.end();it++){
pair<int,parent> x=(*it);
int p=x.second.p;
int edge=x.second.edge;
if(edge==0) X[p-1]=A[j];
else Y[p-1]=A[j];
j++;
}
memo.clear();
/*for(int i=0;i<n;i++){
cout<<X[i]<<" "<<Y[i]<<endl;
}*/
answer(C, X, Y);
}
# | 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... |