QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#704935 | #9519. Build a Computer | chzhc_ | AC ✓ | 6ms | 3816kb | C++14 | 5.4kb | 2024-11-02 21:34:04 | 2024-11-02 21:34:07 |
Judging History
answer
#include <bits/stdc++.h>
template < typename T >
inline void read(T &cnt) {
cnt = 0; char ch = getchar(); bool op = 1;
for (; ! isdigit(ch); ch = getchar())
if (ch == '-') op = 0;
for (; isdigit(ch); ch = getchar())
cnt = cnt * 10 + ch - 48;
cnt = op ? cnt : - cnt;
}
const int N = 200;
int max = 0;
std::vector < std::pair < int, int > > V[N], V2[N];
int change[N], Ichange[N], exi2[N];
inline void ADD(int u, int v, int x) {
exi2[u] = 1, exi2[v] = 1;
max = std::max(max, std::max(u, v));
V[u].push_back(std::make_pair(v, x));
// std::cout << u << ' ' << v << ' ' << x << '\n';
}
bool exi[200];
int nxt[N * N], head[N], to[N * N], val[N * N], In[N], TOT;
inline void add(int u, int v, int x) {
nxt[++ TOT] = head[u];
head[u] = TOT;
to[TOT] = v;
val[TOT] = x;
In[v] ++;
// std::cout << u << ' ' << v << ' ' << x << '\n';
}
int fir, FIR;
int EDGE[200][200][2];
inline void EXadd(int u, int v, int x) {
if (EDGE[u][v][x]) return;
EDGE[u][v][x] = 1;
exi2[u] = 1, exi2[v] = 1;
max = std::max(max, std::max(u, v));
V2[u].push_back(std::make_pair(v, x));
// std::cout << u << ' ' << v << ' ' << x << '\n';
}
inline void search(int u, int exist) {
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
// std::cout << v << 'q';
if (val[i] == 1) {
if (exist == 0) EXadd(FIR, v, 1);
else EXadd(u, v, 1);
search(v, 1);
}
else {
if (exist == 0) search(v, 0);
else EXadd(u, v, 0), search(v, 1);
}
}
}
int size;
inline void solve() {
memset(exi2, 0, sizeof(exi2));
max = 0;
int fir = 0;
for (int i = 1; i <= size; ++ i) {
if (In[i] == 0) fir = i, FIR = i;
}
// std::cout << "JKDSA" << fir << '\n';
search(fir, 0);
int tot = 0;
for (int i = 1; i <= 100; ++ i) {
if (exi2[i]) {
change[i] = ++ tot;
Ichange[tot] = i;
}
}
std::cout << tot << '\n';
for (int i = 1; i <= tot; ++ i) {
int siz = V2[Ichange[i]].size();
std::cout << siz << ' ';
for (int j = 0; j < siz; ++ j) {
// add(i, change[V[Ichange[i]][j].first], V[Ichange[i]][j].second);
std::cout << change[V2[Ichange[i]][j].first] << ' ' << V2[Ichange[i]][j].second << ' ';
}
std::cout << '\n';
}
}
int main()
{
int l, r;
read(l), read(r);
if (l == r) {
int x = 0;
for (int i = 22; i >= 0; -- i)
if ((l >> i) & 1) {
x = i;
break;
}
for (int i = x; i >= 0; -- i) {
if ((l >> i) & 1) {
ADD(i + 2, i + 1, 1);
}
else ADD(i + 2, i + 1, 0);
}
}
else {
int x = 25, x2 = 0, x3;
for (int i = 22; i >= 0; -- i) {
if ((((l >> i) & 1) == 0) && (((r >> i) & 1) == 1)) {
x2 = i; x3 = x;
break;
}
if ((((l >> i) & 1) == 1) && (((r >> i) & 1) == 1)) {
ADD(x, x + 1, 1);
x ++;
}
if ((((l >> i) & 1) == 0) && (((r >> i) & 1) == 0)) {
ADD(x, x + 1, 0);
x ++;
}
}
for (int i = x2; i > 0; -- i) {
if (((l >> i) & 1) == 0) {
if (i == x2) {
ADD(x, x + 1, 0);
x += 1;
}
else {
ADD(x, i + 1, 1);
exi[i + 1] = 1;
ADD(x, x + 1, 0);
x ++;
}
}
else {
ADD(x, x + 1, 1);
x ++;
}
}
if (l & 1) {
ADD(x, 1, 1);
}
else {
ADD(x, 1, 1);
ADD(x, 1, 0);
}
for (int i = x2; i > 0; -- i) {
if (((r >> i) & 1) == 0) {
if (i == x2) {
ADD(x3, x + 1, 0);
x ++;
}
else {
ADD(x, x + 1, 0);
x ++;
}
}
else {
if (i == x2) {
ADD(x3, x + 1, 1);
x ++;
}
else {
ADD(x, i + 1, 0);
exi[i + 1] = 1;
ADD(x, x + 1, 1);
x ++;
}
}
}
if (r & 1) {
ADD(x, 1, 0);
ADD(x, 1, 1);
}
else {
ADD(x, 1, 0);
}
for (int i = 21; i >= 1; -- i) {
if (exi[i]) {
for (int j = i; j >= 2; -- j) {
ADD(j, j - 1, 0), ADD(j, j - 1, 1);
}
break;
}
}
}
int tot = 0;
for (int i = 1; i <= 100; ++ i) {
if (exi2[i]) {
change[i] = ++ tot;
Ichange[tot] = i;
}
}
size = tot;
// std::cout << tot << '\n';
for (int i = 1; i <= tot; ++ i) {
int siz = V[Ichange[i]].size();
// std::cout << siz << ' ';
for (int j = 0; j < siz; ++ j) {
add(i, change[V[Ichange[i]][j].first], V[Ichange[i]][j].second);
// std::cout << change[V[Ichange[i]][j].first] << ' ' << V[Ichange[i]][j].second << ' ';
}
// std::cout << '\n';
}
solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
5 7
output:
5 0 1 3 1 2 5 1 4 0 1 1 1 2 1 1 1 0
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
10 27
output:
12 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 9 1 6 1 2 7 0 3 1 1 8 1 2 1 0 1 1 2 10 1 4 0 1 11 0 2 12 1 2 0 2 1 1 1 0
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
5 13
output:
9 0 2 1 1 1 0 2 2 1 2 0 2 7 1 5 1 2 6 0 2 1 1 1 1 2 8 1 3 0 1 9 0 2 1 1 1 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 6ms
memory: 3656kb
input:
1 1000000
output:
39 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 20 21 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1 1
output:
2 0 1 1 1
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
7 9
output:
7 0 2 5 1 3 1 1 4 1 1 1 1 1 6 0 1 7 0 2 1 1 1 0
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
3 7
output:
6 0 2 1 1 1 0 2 5 1 4 1 1 1 1 2 6 1 2 0 2 1 1 1 0
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
1 5
output:
5 0 2 1 1 1 0 3 4 1 1 1 2 1 1 5 0 2 1 1 1 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1 4
output:
5 0 2 1 1 1 0 3 4 1 1 1 2 1 1 5 0 1 1 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
8 9
output:
5 0 1 3 1 1 4 0 1 5 0 2 1 1 1 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
7 51
output:
13 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 4 9 1 7 1 4 1 5 1 1 8 1 1 1 1 2 10 1 5 0 1 11 0 1 12 0 2 13 1 2 0 2 1 1 1 0
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
51 79
output:
16 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 11 1 6 1 1 7 1 2 8 0 4 1 2 9 0 3 1 1 10 1 1 1 1 1 12 0 1 13 0 2 14 1 4 0 2 15 1 3 0 2 16 1 2 0 2 1 1 1 0
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
92 99
output:
14 0 2 1 1 1 0 1 4 1 2 10 1 5 0 1 6 1 1 7 1 1 8 1 2 9 0 2 1 2 1 0 1 1 1 11 0 1 12 0 1 13 0 2 14 1 2 0 2 1 1 1 0
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
27 36
output:
13 0 2 1 1 1 0 2 2 1 2 0 2 9 1 5 1 1 6 1 2 7 0 3 1 1 8 1 1 1 1 1 10 0 1 11 0 2 12 1 3 0 1 13 0 1 1 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
55 84
output:
17 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 12 1 7 1 1 8 1 2 9 0 4 1 1 10 1 1 11 1 1 1 1 1 13 0 2 14 1 5 0 1 15 0 2 16 1 3 0 1 17 0 1 1 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 4ms
memory: 3816kb
input:
297208 929600
output:
57 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 2 39 1 21 1 2 22 0 18 1 2 23 0 17 1 1 24 1 2 25 0 15 1 2 26 0 14 1 2 27 ...
result:
ok ok
Test #17:
score: 0
Accepted
time: 3ms
memory: 3656kb
input:
45728 589156
output:
54 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 5 36 1 21 1 17 1 18 1 19 1 2 22 0 15 1 1 23 1 1 24 1 2 25 0 12 1 2 26 0 1...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
129152 138000
output:
47 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 31 1 15 1 1 16 1 1 17 1 1 18 1 1 19 1 1 20 1 2 21 0 11 1 2 22 0 10 1 2 23 0 9 1 1 24 1 2 25 0 7 1 2 26 0 6 1 2 27 0 5 1 2 28 0 4 1 2 29 0 3 ...
result:
ok ok
Test #19:
score: 0
Accepted
time: 3ms
memory: 3816kb
input:
245280 654141
output:
56 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 3 38 1 21 1 19 1 1 22 1 1 23 1 2 24 0 15 1 1 25 1 1 26 1 1 27 1 1 28 1 ...
result:
ok ok
Test #20:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
202985 296000
output:
52 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 35 1 18 1 1 19 1 2 20 0 16 1 2 21 0 15 1 2 22 0 14 1 1 23 1 1 24 1 2 25 0 11 1 2 26 0 10 1 2 27 0 9 1 1 2...
result:
ok ok
Test #21:
score: 0
Accepted
time: 3ms
memory: 3736kb
input:
438671 951305
output:
57 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 2 39 1 21 1 1 22 1 2 23 0 17 1 1 24 1 2 25 0 15 1 1 26 1 1 27 1 2 28 0 ...
result:
ok ok
Test #22:
score: 0
Accepted
time: 2ms
memory: 3792kb
input:
425249 739633
output:
56 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 38 1 20 1 1 21 1 2 22 0 17 1 2 23 0 16 1 1 24 1 1 25 1 1 26 1 1 27 1 1 28 1 2 29...
result:
ok ok
Test #23:
score: 0
Accepted
time: 3ms
memory: 3716kb
input:
551207 961718
output:
56 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 1 20 1 2 39 1 21 0 2 22 0 18 1 2 23 0 17 1 2 24 0 16 1 1 25 1 1 26 1 2 27 0 13 1 1 ...
result:
ok ok
Test #24:
score: 0
Accepted
time: 4ms
memory: 3684kb
input:
114691 598186
output:
55 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 4 37 1 21 1 18 1 19 1 1 22 1 1 23 1 2 24 0 14 1 2 25 0 13 1 2 26 0 12 1 ...
result:
ok ok
Test #25:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
234654 253129
output:
46 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 1 16 1 1 17 1 1 18 1 2 33 1 19 0 2 20 0 14 1 1 21 1 2 22 0 12 1 1 23 1 2 24 0 10 1 2 25 0 9 1 1 26 1 2 27 0 7 1 2 28 0 6 1 1 29 1 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
554090 608599
output:
52 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 1 18 1 1 19 0 1 20 0 2 37 1 21 0 2 22 0 16 1 1 23 1 1 24 1 1 25 1 2 26 0 12 1 1 27 1 2 28 0 10 1 2 29 0 9 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed