QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #690081 | #9519. Build a Computer | Fiatiustitia | AC ✓ | 0ms | 3852kb | C++20 | 4.6kb | 2024-10-30 20:12:01 | 2024-10-30 20:12:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mask = (1 << 20) - 1;
void solve()
{
int l, r;
cin >> l >> r;
using P = pair<int, int>;
if (l == r)
{
vector g(101,vector<P>());
int pre = 1,tot = 2;
for(int i = 19;i != -1;i--)
{
if ((1 << i) > r)
continue;
auto m = l >> i & 1;
g[pre].push_back(P(tot,m));
pre = tot;
tot++;
}
cout << tot - 1 << '\n';
for(int i = 1;i < tot;i++)
{
cout << g[i].size() << ' ';
for(auto [l,r] : g[i])
cout << l << ' ' << r << ' ';
cout << '\n';
}
return ;
}
using u32 = int;
u32 rl = 0, lr = 0,pref = 0;
for (u32 i = 19; i != -1; i--)
{
auto ml = l >> i & 1, mr = r >> i & 1;
if ((1 << i) > r || (ml == mr))
{
pref |= ml << i;
continue;
}
rl = (1 << i);
lr = (1 << i) - 1;
rl |= pref;
lr |= pref;
break;
}
vector g(101, vector<P>());
int term = -1;
// [rl,r]
u32 s = 1;
int tot = 2;
{
u32 pre = s;
bool fuck = 0;
auto ptot = tot;
for (u32 i = 19; i != -1; i--)
{
if ((1 << i) > r)
continue;
auto m0 = r >> i & 1;
auto m1 = rl >> i & 1;
g[pre].push_back(P(i ? tot : term, m1));
if (fuck)
g[pre].push_back(P(i ? tot : term, 1));
if (m0 != m1)
fuck = 1;
pre = tot;
tot++;
}
tot--;
// [ptot,tot)
auto xx = ptot;
pre = s;
fuck = 0;
for (u32 i = 19; i != -1; i--)
{
if ((1 << i) > r)
continue;
auto m0 = r >> i & 1;
auto m1 = rl >> i & 1;
if (m0 != m1)
fuck = 1;
if (fuck)
{
g[pre].push_back(P(i ? tot : term, m0));
if (m0)
g[pre].push_back(P(i ? xx : term, 0));
pre = tot;
tot++;
}
else if (m0 == m1)
pre = xx;
xx++;
}
tot -= fuck;
}
// [l,lr]
{
u32 pre = s;
auto ptot = tot;
bool fuck = 0;
for (u32 i = 19; i != -1; i--)
{
if ((1 << i) > lr)
continue;
auto m0 = lr >> i & 1;
auto m1 = l >> i & 1;
g[pre].push_back(P(i ? tot : term, m0));
if (fuck)
g[pre].push_back(P(i ? tot : term, 0));
if (m0 != m1)
fuck = 1;
pre = tot;
tot++;
}
tot--;
auto xx = ptot;
pre = s;
fuck = 0;
bool fff = false;
for (u32 i = 19; i != -1; i--)
{
if ((1 << i) > lr)
continue;
auto m0 = lr >> i & 1;
auto m1 = l >> i & 1;
if (m0 != m1)
fuck = 1;
fff |= m1;
if (fuck)
{
if (!fff)
{
g[pre].push_back(P(xx,1));
}
else
{
g[pre].push_back(P(i ? tot : term, m1));
if (m1 == 0)
g[pre].push_back(P(i ? xx : term, 1));
pre = tot;
tot++;
}
}
else if (!fuck || !fff)
pre = xx;
xx++;
}
tot -= fuck;
}
for(int i = 1;i < tot;i++)
{
for(auto &[p,w] : g[i])
{
if (p == -1)
p = tot;
}
}
tot++;
cout << tot - 1 << '\n';
for(int i = 1;i < tot;i++)
{
sort(g[i].begin(),g[i].end());
g[i].resize(unique(g[i].begin(),g[i].end()) - g[i].begin());
cout << g[i].size() << ' ';
for(auto [p,w] : g[i])
cout << p << ' ' << w << ' ';
cout << '\n';
}
}
int main()
{
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
auto _ = clock();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
#ifdef LOCAL
cerr << clock() - _ << '\n';
#endif
return 0;
}
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
input:
5 7
output:
6 2 2 1 4 1 1 3 1 2 6 0 6 1 1 5 0 1 6 1 0
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
10 27
output:
14 2 2 1 9 1 2 3 0 6 1 2 4 0 4 1 2 5 0 5 1 2 14 0 14 1 1 7 0 2 5 0 8 1 2 14 0 14 1 2 10 1 12 0 2 11 0 11 1 2 14 0 14 1 1 13 1 2 14 0 14 1 0
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
5 13
output:
10 2 2 1 7 1 2 3 0 5 1 2 4 0 4 1 2 10 0 10 1 1 6 0 2 10 0 10 1 2 8 1 9 0 2 10 0 10 1 1 10 1 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
1 1000000
output:
57 20 2 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 2 3 0 21 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 ...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
7 9
output:
7 2 2 1 5 1 1 3 0 1 4 0 2 7 0 7 1 1 6 1 1 7 1 0
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
3 7
output:
6 2 2 1 5 1 2 3 0 4 1 2 6 0 6 1 2 6 0 6 1 1 6 1 0
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
1 5
output:
5 3 2 1 4 1 5 1 1 3 0 2 5 0 5 1 2 5 0 5 1 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
1 4
output:
5 3 2 1 4 1 5 1 1 3 0 1 5 0 2 5 0 5 1 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
8 9
output:
8 2 2 1 5 1 1 3 0 1 4 0 1 8 1 1 6 0 1 7 0 1 8 0 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
7 51
output:
17 4 2 1 11 1 12 1 15 1 2 3 0 7 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 17 0 17 1 1 8 0 1 9 0 2 6 0 10 1 2 17 0 17 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 17 0 17 1 1 16 1 1 17 1 0
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
51 79
output:
19 2 2 1 11 1 1 3 0 1 4 0 2 5 0 8 1 2 6 0 6 1 2 7 0 7 1 2 19 0 19 1 2 6 0 9 1 2 7 0 10 1 2 19 0 19 1 1 12 1 2 13 1 16 0 2 14 0 14 1 2 15 0 15 1 2 19 0 19 1 2 14 1 17 0 1 18 1 1 19 1 0
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
92 99
output:
16 2 2 1 9 1 1 3 1 1 4 0 1 5 0 1 6 0 2 7 0 8 1 2 16 0 16 1 2 16 0 16 1 1 10 0 1 11 1 1 12 1 1 13 1 2 14 1 15 0 2 16 0 16 1 2 16 0 16 1 0
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
27 36
output:
15 2 2 1 9 1 1 3 0 1 4 0 2 5 0 7 1 2 6 0 6 1 2 15 0 15 1 1 8 0 1 15 0 1 10 1 2 11 1 13 0 2 12 0 12 1 2 15 0 15 1 1 14 1 1 15 1 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
55 84
output:
20 2 2 1 12 1 1 3 0 2 4 0 8 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 20 0 20 1 1 9 0 2 6 0 10 1 1 11 0 1 20 0 1 13 1 2 14 1 17 0 2 15 0 15 1 2 16 0 16 1 2 20 0 20 1 1 18 1 1 19 1 1 20 1 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
297208 929600
output:
74 2 2 1 39 1 2 3 0 21 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 74 0 74 1 2 4 0 22 1 1 23 0 1 24 0 1 25 0 2 8 0 26 1 1 2...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
45728 589156
output:
69 5 2 1 36 1 37 1 38 1 54 1 1 3 0 1 4 0 1 5 0 2 6 0 21 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 69 0 69 1 2 7 0 22 1 2 8 0 23 1 2 9 0 24 1 2 10 0 25 1 ...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
129152 138000
output:
57 2 2 1 31 1 1 3 0 1 4 0 1 5 0 1 6 0 2 7 0 19 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 57 0 57 1 2 8 0 20 1 1 21 0 2 10 0 22 1 2 11 0 23 1 1 24 0 1 25 0 1 26 0 2 15 0 27 1 1 28 0 1 ...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
245280 654141
output:
72 3 2 1 37 1 55 1 1 3 0 1 4 0 2 5 0 21 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 72 0 72 1 2 6 0 22 1 2 7 0 23 1 2 8 0 24 1 2 9 0 25 1 2 10 0...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
202985 296000
output:
67 2 2 1 35 1 1 3 0 1 4 0 2 5 0 20 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 67 0 67 1 1 21 0 1 22 0 1 23 0 1 24 0 2 10 0 25 1 1 26 0 1 27 0 1 28 0 2 1...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
438671 951305
output:
73 2 2 1 39 1 2 3 0 21 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 73 0 73 1 2 4 0 22 1 1 23 0 2 6 0 24 1 1 25 0 1 26 0 1 2...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
425249 739633
output:
72 2 2 1 38 1 1 3 0 2 4 0 21 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 72 0 72 1 2 5 0 22 1 1 23 0 2 7 0 24 1 1 25 0 1 26 0 2 10 0 ...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
551207 961718
output:
74 2 2 1 38 1 1 3 1 2 4 0 21 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 74 0 74 1 1 22 0 2 6 0 23 1 1 24 0 2 8 0 25 1 1 26 0 2 10 0 ...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
114691 598186
output:
71 4 2 1 37 1 38 1 55 1 1 3 0 1 4 0 2 5 0 21 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 71 0 71 1 1 22 0 1 23 0 2 8 0 24 1 1 25 0 1 26 0 1 27 ...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
234654 253129
output:
61 2 2 1 31 1 1 3 1 1 4 1 1 5 1 1 6 0 2 7 0 19 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 61 0 61 1 2 8 0 20 1 2 9 0 21 1 1 22 0 1 23 0 2 12 0 24 1 2 13 0 25 1 1 26 0 1 27 0 2 16 0 28 1...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
554090 608599
output:
69 2 2 1 35 1 1 3 0 1 4 0 1 5 1 1 6 0 2 7 0 21 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 69 0 69 1 1 22 0 1 23 0 2 10 0 24 1 1 25 0 1 26 0 2 13 0 27 1 1 28 0 2...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed