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;
using vi = vector<int>;
vi X, Y;
vector<pair<int, int> > VP;
int gen(int niv, int nr) {
int id = X.size();
X.push_back(0);
Y.push_back(0);
//cout << niv << " " << nr << "\n";
if(niv == 1 && nr == 2) {
return -id - 1;
} else if(niv == 1 && nr == 1) {
X[id] = -1;
return -id - 1;
}
if(nr <= (1 << (niv - 1))) {
int S = gen(niv - 1, nr);
Y[id] = S;
X[id] = -1;
return -id - 1;
} else {
Y[id] = gen(niv - 1, (1 << (niv - 1)));
X[id] = gen(niv - 1, nr - (1 << (niv - 1)));
return -id - 1;
}
return -id - 1;
}
void create_circuit(int M, vi A) {
A.push_back(0);
map<int, int> Fr;
int frmax = 0;
for(auto it : A) {
++Fr[it];
frmax = max(frmax, Fr[it]);
}
if(frmax <= 4) {
int ult = 0;
vector<vi> Urm(M + 1);
for(int i = 0; i < A.size(); ++i) {
Urm[ult].push_back(A[i]);
ult = A[i];
}
vi C(M + 1, -1), X, Y;
for(int i = 0; i <= M; ++i) {
if(Urm[i].empty()) {
C[i] = 0;
continue;
}
if(Urm[i].size() == 1) {
C[i] = Urm[i][0];
continue;
}
if(Urm[i].size() == 2) {
X.push_back(Urm[i][0]);
Y.push_back(Urm[i][1]);
C[i] = -X.size();
continue;
}
if(Urm[i].size() == 3) {
int id = X.size();
X.push_back(-id-2);
Y.push_back(-id-3);
X.push_back(Urm[i][0]);
Y.push_back(Urm[i][1]);
X.push_back(-id - 1);
Y.push_back(Urm[i][2]);
C[i] = -id - 1;
continue;
}
if(Urm[i].size() == 4) {
int id = X.size();
X.push_back(-id-2);
Y.push_back(-id-3);
X.push_back(Urm[i][0]);
Y.push_back(Urm[i][2]);
X.push_back(Urm[i][1]);
Y.push_back(Urm[i][3]);
C[i] = -id - 1;
continue;
}
assert(0);
}
// cout << "C: ";
// for(auto it : C)
// cout << it << " ";
// cout << "\n";
// cout << "X: ";
// for(auto it : X)
// cout << it << " ";
// cout << "\n";
// cout << "Y: ";
// for(auto it : Y)
// cout << it << " ";
// cout << "\n";
answer(C, X, Y);
} else {
int niv = 1;
while((1 << niv) <= A.size()) ++niv;
gen(niv, A.size());
vi C(M + 1, -1);
vi Stare(X.size(), 0);
int u = -1, p = 0;
////cout << "ASSIGN\n";
do {
if(u > 0) {
u = -1;
}
int id = -u - 1;
if(!Stare[id]) {
Stare[id] ^= 1;
if(X[id]) u = X[id];
else {
u = X[id] = A[p++];
}
} else {
Stare[id] ^= 1;
if(Y[id]) u = Y[id];
else {
u = Y[id] = A[p++];
}
}
} while(u != 0);
int nr0 = 0;
for(auto &it : X) nr0 += !it;
for(auto &it : Y) nr0 += !it;
//cout << "In total " << nr0 << "\n";
//for(auto it : Stare)
//cout << it << " ";
//cout << "\n";
//cout << "C: ";
//for(auto it : C)
//cout << it << " ";
//cout << "\n";
//cout << "X: ";
//for(auto it : X)
//cout << it << " ";
//cout << "\n";
//cout << "Y: ";
//for(auto it : Y)
//cout << it << " ";
//cout << "\n";
answer(C, X, Y);
}
}
Compilation message (stderr)
doll.cpp: In function 'void create_circuit(int, vi)':
doll.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 0; i < A.size(); ++i) {
| ~~^~~~~~~~~~
doll.cpp:109:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | while((1 << niv) <= A.size()) ++niv;
| ~~~~~~~~~~~^~~~~~~~~~~
# | 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... |