#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef pair<int, vi> ivi;
#define pb push_back
#define f first
#define s second
namespace debug {
const int DEBUG = false;
template<class T1, class T2>
void pr(const pair<T1, T2> &x);
template<class T, size_t SZ>
void pr(const array<T, SZ> &x);
template<class T>
void pr(const vector<T> &x);
template<class T>
void pr(const set<T> &x);
template<class T1, class T2>
void pr(const map<T1, T2> &x);
template<class T>
void pr(const T &x) { if (DEBUG) cout << x; }
template<class T, class... Ts>
void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }
template<class T1, class T2>
void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }
template<class T>
void prIn(const T &x) {
pr("{");
bool fst = 1;
for (auto &a : x) {
pr(fst ? "" : ", ", a), fst = 0;
}
pr("}");
}
template<class T, size_t SZ>
void pr(const array<T, SZ> &x) { prIn(x); }
template<class T>
void pr(const vector<T> &x) { prIn(x); }
template<class T>
void pr(const set<T> &x) { prIn(x); }
template<class T1, class T2>
void pr(const map<T1, T2> &x) { prIn(x); }
void ps() { pr("\n"); }
template<class Arg, class... Args>
void ps(const Arg &first, const Args &... rest) {
pr(first, " ");
ps(rest...);
}
}
using namespace debug;
void answer(vi C, vi X, vi Y);
vi cAns;
vi xAns;
vi yAns;
int nS = 1;
ivi construct(int i) {
if (i == 2) {
ivi ret = {nS, {nS, -nS}};
nS++;
ps("vS1:", i, ret.s.size());
return ret;
} else if (i == 3) {
ps(nS + 1, -nS);
xAns[nS] = -(nS + 1);
yAns[nS] = -(nS + 2);
yAns[nS + 1] = -nS;
ivi ret = {nS, {nS + 1, nS + 2, -(nS + 2)}};
nS += 3;
ps("vS2:", i, ret.s.size());
return ret;
}
if (i & 1) {
int n = (i + 1) / 2;
ivi a = construct(n);
ivi b = construct(n);
xAns[nS] = -a.f;
yAns[nS] = -b.f;
int aLast = a.second[a.second.size() - 1];
ps(aLast, nS);
if (aLast >= 0) {
xAns[aLast] = -nS;
} else {
yAns[-aLast] = -nS;
}
vi ret;
for (int i = 0; i < n - 1; i++) {
ret.pb(a.s[i]);
ret.pb(b.s[i]);
}
ret.pb(b.s[n - 1]);
ps("vS:", i, ret.size());
return {nS++, ret};
} else {
int n = i / 2;
ivi a = construct(n);
ivi b = construct(n);
xAns[nS] = -a.f;
yAns[nS] = -b.f;
vi ret;
for (int j = 0; j < n; j++) {
ret.pb(a.s[j]);
ret.pb(b.s[j]);
}
return {nS++, ret};
}
}
void create_circuit(int M, vi ord) {
ps("acc");
int N = ord.size();
cAns.resize(M + 1);
xAns.resize(2 * N + 1);
yAns.resize(2 * N + 1);
vi cnt(M + 1);
for (int i = 0; i < N; i++) {
cnt[ord[i]]++;
}
vector<vi> out(M + 1);
vi used(M + 1);
for (int i = 1; i <= M; i++) {
if (cnt[i] > 1) {
ivi inf = construct(cnt[i]);
ps("inf:", i, inf);
cAns[i] = -inf.f;
out[i] = inf.s;
}
}
ps("cnt[1]:", cnt[1]);
ps("out:", out);
ps("used:", used);
ps(xAns);
ps(yAns);
cAns[0] = ord[0];
for (int i = 0; i + 1 < N; i++) {
int cV = ord[i];
int nV = ord[i + 1];
if (cnt[cV] == 1) {
cAns[cV] = nV;
} else {
int link = out[cV][used[cV]++];
ps("con", i, nV, link);
if (link >= 0) {
xAns[link] = nV;
} else {
yAns[-link] = nV;
}
}
}
int cV = ord[N - 1];
int nV = 0;
if (cnt[cV] == 1) {
cAns[cV] = nV;
} else {
int link = out[cV][used[cV]++];
if (link >= 0) {
xAns[link] = nV;
} else {
yAns[-link] = nV;
}
}
ps(xAns);
ps(yAns);
vi nX(xAns.begin() + 1, xAns.begin() + nS);
vi nY(yAns.begin() + 1, yAns.begin() + nS);
ps(nX);
ps(nY);
ps(cAns);
answer(cAns, nX, nY);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
37 ms |
6120 KB |
Output is correct |
3 |
Correct |
30 ms |
4672 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
20 ms |
4556 KB |
Output is correct |
6 |
Correct |
31 ms |
6952 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
37 ms |
6120 KB |
Output is correct |
3 |
Correct |
30 ms |
4672 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
20 ms |
4556 KB |
Output is correct |
6 |
Correct |
31 ms |
6952 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
70 ms |
9796 KB |
Output is correct |
9 |
Correct |
87 ms |
9924 KB |
Output is correct |
10 |
Correct |
137 ms |
14780 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
2 ms |
204 KB |
Output is correct |
13 |
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 |
37 ms |
6120 KB |
Output is correct |
3 |
Correct |
30 ms |
4672 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
20 ms |
4556 KB |
Output is correct |
6 |
Correct |
31 ms |
6952 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
70 ms |
9796 KB |
Output is correct |
9 |
Correct |
87 ms |
9924 KB |
Output is correct |
10 |
Correct |
137 ms |
14780 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
2 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
124 ms |
14552 KB |
Output is correct |
15 |
Correct |
68 ms |
8132 KB |
Output is correct |
16 |
Correct |
99 ms |
12176 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
108 ms |
14132 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
204 KB |
Output is partially correct |
2 |
Correct |
75 ms |
7644 KB |
Output is correct |
3 |
Partially correct |
100 ms |
13232 KB |
Output is partially correct |
4 |
Partially correct |
167 ms |
13900 KB |
Output is partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
204 KB |
Output is partially correct |
2 |
Correct |
75 ms |
7644 KB |
Output is correct |
3 |
Partially correct |
100 ms |
13232 KB |
Output is partially correct |
4 |
Partially correct |
167 ms |
13900 KB |
Output is partially correct |
5 |
Partially correct |
140 ms |
14508 KB |
Output is partially correct |
6 |
Partially correct |
132 ms |
14776 KB |
Output is partially correct |
7 |
Partially correct |
159 ms |
14648 KB |
Output is partially correct |
8 |
Partially correct |
153 ms |
14904 KB |
Output is partially correct |
9 |
Partially correct |
106 ms |
10136 KB |
Output is partially correct |
10 |
Partially correct |
150 ms |
15024 KB |
Output is partially correct |
11 |
Partially correct |
165 ms |
15164 KB |
Output is partially correct |
12 |
Partially correct |
105 ms |
10024 KB |
Output is partially correct |
13 |
Partially correct |
99 ms |
9780 KB |
Output is partially correct |
14 |
Partially correct |
87 ms |
9760 KB |
Output is partially correct |
15 |
Partially correct |
77 ms |
9540 KB |
Output is partially correct |
16 |
Partially correct |
5 ms |
588 KB |
Output is partially correct |
17 |
Partially correct |
84 ms |
8644 KB |
Output is partially correct |
18 |
Partially correct |
84 ms |
8644 KB |
Output is partially correct |
19 |
Partially correct |
83 ms |
8996 KB |
Output is partially correct |
20 |
Partially correct |
121 ms |
12212 KB |
Output is partially correct |
21 |
Partially correct |
176 ms |
13736 KB |
Output is partially correct |
22 |
Partially correct |
123 ms |
11824 KB |
Output is partially correct |