#include "doll.h"
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define st first
#define nd second
#define rd third
#define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
#define RE(i, n) FOR(i, 1, n)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define REP(i, n) for(int i = 0;i <(n); ++i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define cerr if(0)cout
#endif
#define next ____next
#define prev ____prev
#define left ____left
#define hash ____hash
typedef long long ll;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<pair<int, int> > VPII;
typedef vector<pair<ll, ll> > VPLL;
template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
template<class T1, class T2>
ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
template<class A, class B, class C> struct Triple { A first; B second; C third;
bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
template<class T> void ResizeVec(T&, vector<int>) {}
template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
for (T& v : vec) { ResizeVec(v, sz); }
}
typedef Triple<int, int, int> TIII;
template<class A, class B, class C>
ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class L, class R> ostream& operator<<(ostream& out, map<L, R> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
vector<int> C(M + 1, -1);
C[0] = A[0];
vector<int> X, Y;
A.PB(0);
A.erase(A.begin());
function<int(int, int, int)> Go = [&](int cur_node, int sz, int rem_hei) {
debug(cur_node, sz, rem_hei);
if (sz == 0) { return 0; }
if (rem_hei == 0) {
if (sz == 2) {
X.PB(0);
Y.PB(0);
return 1;
}
if (sz == 1) {
X.PB(-1);
Y.PB(0);
return 1;
}
debug(sz);
assert(false);
}
int to_left = 1;
while (2 * to_left <= min(sz, 1 << (rem_hei))) {
to_left *= 2;
}
int to_right = sz - to_left;
X.PB(-(cur_node + 1));
Y.PB(0);
int lsz = Go(cur_node + 1, to_left, rem_hei - 1);
debug(SZ(Y), cur_node);
Y[cur_node - 1] = -(cur_node + 1 + lsz);
//return lsz +
int rsz = Go(cur_node + 1 + lsz, to_right, rem_hei - 1);
if (rsz == 0) {
Y[cur_node - 1] = -1;
swap(X[cur_node - 1], Y[cur_node - 1]);
}
return lsz + rsz + 1;
};
int hei = 0;
int outs = 2;
while (outs < N) {
outs *= 2;
hei++;
}
Go(1, N, hei);
debug(X);
debug(Y);
VI st(2 * N + 5);
for (auto goal : A) {
debug(goal);
int cur_node = 1;
while (1) {
debug(cur_node);
int to = -1;
if (st[cur_node] == 0) {
to = -X[cur_node - 1];
} else {
to = -Y[cur_node - 1];
}
if (to == 0) {
if (st[cur_node] == 0) {
X[cur_node - 1] = goal;
} else {
Y[cur_node - 1] = goal;
}
st[cur_node] ^= 1;
break;
} else {
st[cur_node] ^= 1;
cur_node = to;
}
}
}
debug(X);
debug(Y);
debug(st);
answer(C, X, Y);
}
Compilation message
doll.cpp: In function 'void _dbg(const char*, TH, TA ...)':
doll.cpp:20:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
20 | while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
| ^~~~~
doll.cpp:20:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
20 | while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
| ^~~~
doll.cpp: In lambda function:
doll.cpp:72:11: warning: left operand of comma operator has no effect [-Wunused-value]
72 | debug(cur_node, sz, rem_hei);
| ^~~~~~~~
doll.cpp:26:21: note: in definition of macro 'debug'
26 | #define debug(...) (__VA_ARGS__)
| ^~~~~~~~~~~
doll.cpp:72:25: warning: right operand of comma operator has no effect [-Wunused-value]
72 | debug(cur_node, sz, rem_hei);
| ^~~~~~~
doll.cpp:26:21: note: in definition of macro 'debug'
26 | #define debug(...) (__VA_ARGS__)
| ^~~~~~~~~~~
doll.cpp:85:13: warning: statement has no effect [-Wunused-value]
26 | #define debug(...) (__VA_ARGS__)
| ~~~~~~~~~~~~~
......
85 | debug(sz);
doll.cpp:26:21: note: in definition of macro 'debug'
26 | #define debug(...) (__VA_ARGS__)
| ^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:113:9: warning: statement has no effect [-Wunused-value]
26 | #define debug(...) (__VA_ARGS__)
| ~~~~~~~~~~~~~
......
113 | debug(X);
doll.cpp:26:21: note: in definition of macro 'debug'
26 | #define debug(...) (__VA_ARGS__)
| ^~~~~~~~~~~
doll.cpp:114:9: warning: statement has no effect [-Wunused-value]
26 | #define debug(...) (__VA_ARGS__)
| ~~~~~~~~~~~~~
......
114 | debug(Y);
doll.cpp:26:21: note: in definition of macro 'debug'
26 | #define debug(...) (__VA_ARGS__)
| ^~~~~~~~~~~
doll.cpp:117:11: warning: statement has no effect [-Wunused-value]
26 | #define debug(...) (__VA_ARGS__)
| ~~~~~~~~~~~~~
......
117 | debug(goal);
doll.cpp:26:21: note: in definition of macro 'debug'
26 | #define debug(...) (__VA_ARGS__)
| ^~~~~~~~~~~
doll.cpp:120:13: warning: statement has no effect [-Wunused-value]
26 | #define debug(...) (__VA_ARGS__)
| ~~~~~~~~~~~~~
......
120 | debug(cur_node);
doll.cpp:26:21: note: in definition of macro 'debug'
26 | #define debug(...) (__VA_ARGS__)
| ^~~~~~~~~~~
doll.cpp:142:9: warning: statement has no effect [-Wunused-value]
26 | #define debug(...) (__VA_ARGS__)
| ~~~~~~~~~~~~~
......
142 | debug(X);
doll.cpp:26:21: note: in definition of macro 'debug'
26 | #define debug(...) (__VA_ARGS__)
| ^~~~~~~~~~~
doll.cpp:143:9: warning: statement has no effect [-Wunused-value]
26 | #define debug(...) (__VA_ARGS__)
| ~~~~~~~~~~~~~
......
143 | debug(Y);
doll.cpp:26:21: note: in definition of macro 'debug'
26 | #define debug(...) (__VA_ARGS__)
| ^~~~~~~~~~~
doll.cpp:6:12: warning: statement has no effect [-Wunused-value]
6 | #define st first
| ^
doll.cpp:26:21: note: in definition of macro 'debug'
26 | #define debug(...) (__VA_ARGS__)
| ^~~~~~~~~~~
doll.cpp:144:9: note: in expansion of macro 'st'
144 | debug(st);
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
49 ms |
4032 KB |
Output is correct |
3 |
Correct |
46 ms |
3776 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
13 ms |
1356 KB |
Output is correct |
6 |
Incorrect |
67 ms |
5436 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
49 ms |
4032 KB |
Output is correct |
3 |
Correct |
46 ms |
3776 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
13 ms |
1356 KB |
Output is correct |
6 |
Incorrect |
67 ms |
5436 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
49 ms |
4032 KB |
Output is correct |
3 |
Correct |
46 ms |
3776 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
13 ms |
1356 KB |
Output is correct |
6 |
Incorrect |
67 ms |
5436 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
68 ms |
5768 KB |
Output is correct |
3 |
Correct |
78 ms |
5356 KB |
Output is correct |
4 |
Partially correct |
128 ms |
8116 KB |
Output is partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
68 ms |
5768 KB |
Output is correct |
3 |
Correct |
78 ms |
5356 KB |
Output is correct |
4 |
Partially correct |
128 ms |
8116 KB |
Output is partially correct |
5 |
Partially correct |
137 ms |
8660 KB |
Output is partially correct |
6 |
Partially correct |
138 ms |
8348 KB |
Output is partially correct |
7 |
Partially correct |
139 ms |
8356 KB |
Output is partially correct |
8 |
Partially correct |
126 ms |
8244 KB |
Output is partially correct |
9 |
Correct |
93 ms |
5432 KB |
Output is correct |
10 |
Partially correct |
125 ms |
8096 KB |
Output is partially correct |
11 |
Partially correct |
167 ms |
8084 KB |
Output is partially correct |
12 |
Correct |
79 ms |
5360 KB |
Output is correct |
13 |
Correct |
71 ms |
5896 KB |
Output is correct |
14 |
Correct |
88 ms |
5648 KB |
Output is correct |
15 |
Correct |
89 ms |
5644 KB |
Output is correct |
16 |
Correct |
3 ms |
460 KB |
Output is correct |
17 |
Correct |
70 ms |
5772 KB |
Output is correct |
18 |
Correct |
73 ms |
5760 KB |
Output is correct |
19 |
Correct |
84 ms |
5436 KB |
Output is correct |
20 |
Partially correct |
132 ms |
8172 KB |
Output is partially correct |
21 |
Partially correct |
134 ms |
8032 KB |
Output is partially correct |
22 |
Partially correct |
156 ms |
8108 KB |
Output is partially correct |