#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
int m;
int n;
int MAXN=1;
int depth=0;
vector<int> C;
vector<int> X;
vector<int> Y;
void update(int pos, int val) {
pos+=MAXN;
//cout <<"UPDATED " << pos <<" "<< val << endl;
if (pos%2==0) {
X[pos/2] = val;
}
else {
Y[pos/2] = val;
}
pos/=2;
while (pos>1) {
int par=pos/2;
if (pos%2==0) {
X[par] = -pos;
}
else {
Y[par] = -pos;
}
pos=par;
}
}
int binrev(int v) {
vector<int> bits;
while (v) {
bits.push_back(v%2);
v/=2;
}
int x=0;
for (auto i:bits) {
x*=2;
x+=i;
}
return x;
}
int timer(int k) {
vector<int> bits;
for (int i=0; i<depth; i++) {
bits.push_back(k%2);
k/=2;
}
int x=0;
for (auto i:bits) {
x*=2;
x+=i;
}
return x;
}
vector<int> times;
void create_circuit(signed M, vector<signed> A) {
int N = A.size();
N++;
A.push_back(0);
//top of the tree = 1
//sons of i are 2*i and 2*i+1
for (int i=1; i<100; i++) {
MAXN*=2;
if (MAXN>=N) {
depth=i;
break;
}
}
times=vector<int>(MAXN,-1);
for (int i=0; i<MAXN; i++) {
times[i] = timer(i);
}
for (int i=0; i<8; i++) {
//cout << i <<" " << time(i) << endl;
}
int S=MAXN;
C=vector<int>(M+1,-1);
X=vector<int>(S+1,-1);
Y=vector<int>(S+1,-1);
C[0] = -1;
int lef=MAXN/2;
int ri=N-lef;
vector<int> elems;
for (int i=0; i<lef; i++) {
//cout << i <<" " << binrev(i) << endl;
elems.push_back(i);
}
for (int i=MAXN-ri; i<MAXN; i++) {
elems.push_back(i);
}
sort(elems.begin(), elems.end(), [&](const int a, const int b) {
return times[a]<times[b];
});
//cout << "ELEMS" << endl;
//for (auto i:elems) {
// cout << i <<" ";
// }
//cout << endl;
assert(elems.size()==N);
for (int i=0; i<elems.size(); i++) {
update(elems[i], A[i]);
}
//cout << "DONE1" << " " << M << " " << S << " " << S <<" " <<endl;
vector<signed> C2;
vector<signed> X2;
vector<signed> Y2;
//cout << "DONE3" << endl;
for (int i=0; i<C.size(); i++) {
//cout << i <<" " << C.size() << " " << C[i] << " " << M+1 << endl;
C2.push_back(C[i]);
}
for (int i=1; i<=S; i++) {
X2.push_back(X[i]);
}
for (int i=1; i<=S; i++) {
Y2.push_back(Y[i]);
}
//cout << "DONE2" << endl;
set<int> used;
for (auto i:X2) {
if (i>=0) {
continue;
}
used.insert(-i);
}
for (auto i:Y2) {
if (i>=0) {
continue;
}
used.insert(-i);
}
vector<int> vued;
for (auto i:used) {
vued.push_back(i);
}
cout << used.size() << endl;
int us = used.size();
vector<int> revmap(S+3,-1);
for (int i=0; i<us; i++) {
cout << i <<" " << vued[i] << endl;
revmap[vued[i]] = i;
}
//cout << "DONE" << endl;
vector<signed> C3(M+1);
for (int i=0; i<=M; i++) {
C3[i] = C[i];
}
vector<signed> X3(us,-888);
for (int i=0; i<S; i++) {
if (!(used.count(i+1))) {
continue;
}
X3[revmap[i+1]] = (X2[i]<0?-revmap[-X2[i]]-1:X2[i]);
}
vector<signed> Y3(us,-888);
for (int i=0; i<S; i++) {
if (!(used.count(i+1))) {
continue;
}
cout << "doing " << i <<" " << revmap[i+1] <<" "<< -Y2[i] << endl;
Y3[revmap[i+1]] = (Y2[i]<0?-revmap[-Y2[i]]-1:Y2[i]);
}
cout << "original" << endl;
for (int i=0; i<S; i++) {
cout << i <<" " << X2[i] <<" " << Y2[i] << endl;
}
cout << "compressed" << endl;
for (int i=0; i<us; i++) {
cout << i <<" " << X3[i] <<" " << Y3[i] << endl;
}
//cout << "DONE2" << endl;
A.pop_back();
N--;
//cout << "DONE" << endl;
answer(C3, X3, Y3);
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from doll.cpp:2:
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:106:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
106 | assert(elems.size()==N);
| ~~~~~~~~~~~~^~~
doll.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for (int i=0; i<elems.size(); i++) {
| ~^~~~~~~~~~~~~
doll.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (int i=0; i<C.size(); i++) {
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
