QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#712719 | #9519. Build a Computer | Willis | AC ✓ | 1ms | 3968kb | C++20 | 5.1kb | 2024-11-05 16:46:11 | 2024-11-05 16:46:15 |
Judging History
answer
#ifdef local
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#endif
// #pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#ifndef local
#define endl '\n'
#endif
#define pb emplace_back
#define fi first
#define se second
#define rep(i, l, r) for (long long i = l; i <= r; i++)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, x) memset(a, x, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
const double pi = acos(-1);
typedef __int128_t int128;
const db eps = 1e-9;
std::mt19937_64 rng(time(0));
ll my_random(ll l, ll r)
{
uniform_int_distribution<int> range(l, r);
return range(rng);
}
void __()
{
#ifdef local
system("pause");
#endif
}
ll qp(ll a, ll b, ll mod)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
const int maxn = 1e5 + 10;
const ll mod = 998244353;
int trie[110][2];
set<P> val[110];
int nodenum = 1;
vector<P> edge[110];
int endpos;
void insert(vector<int> s, int v)
{
int len = s.size();
int st = 1;
if (s.size() == 1)
{
val[1].insert(P{s[0], v});
}
else
for (int i = 0; i < len - 1; i++)
{
if (trie[st][s[i]] == 0)
trie[st][s[i]] = ++nodenum;
st = trie[st][s[i]];
if (i == len - 2)
{
// cout << st << endl;
val[st].insert(P{s[len - 1], v});
}
}
}
void dfs(int i)
{
// cout << "YY " << i << endl;
for (int j = 0; j <= 1; j++)
{
if (trie[i][j] != 0)
{
dfs(trie[i][j]);
edge[i].pb(P{trie[i][j], j});
}
}
if (val[i].size() != 0)
{
// cout << "XX " << i << endl;
for (auto x : val[i])
edge[i].pb(P{endpos - x.se, x.fi});
}
}
struct node
{
vector<int> l, r;
node() {};
node(vector<int> _l, vector<int> _r) { l = _l, r = _r; };
};
vector<node> vec;
void wk(vector<int> bitl, vector<int> bitr)
{
int start = bitl.size() - 1;
for (int i = 0; i < bitl.size() - 1; i++)
{
if (bitl[i] != bitr[i])
{
start = i;
break;
}
}
if (bitl[bitl.size() - 1] == 0)
{
vector<int> vec2 = bitl;
vec2[bitl.size() - 1] = 1;
vec.pb(node(bitl, vec2));
}
else
{
vec.pb(node(bitl, bitl));
}
for (int i = bitl.size() - 2; i > start; i--)
{
if (bitl[i] == 0)
{
vector<int> b2 = bitl;
b2[i] = 1;
for (int j = i + 1; j < b2.size(); j++)
b2[j] = 0;
vector<int> b3 = b2;
for (int j = i + 1; j < b3.size(); j++)
b3[j] = 1;
vec.pb(node(b2, b3));
bitl = b3;
}
}
vector<int> l1 = bitr;
for (int i = start + 1; i < bitr.size(); i++)
l1[i] = 0;
for (int i = start + 1; i < bitr.size() - 1; i++)
{
if (bitr[i] == 1)
{
vector<int> b2 = bitr;
b2[i] = 0;
for (int j = i + 1; j < b2.size(); j++)
b2[j] = 1;
vec.pb(node(l1, b2));
vector<int> b3 = bitr;
for (int j = i + 1; j < b3.size(); j++)
b3[j] = 0;
l1 = b3;
}
}
vec.pb(node(l1, bitr));
}
int main()
{
IOS;
int l, r;
cin >> l >> r;
vector<int> bitl, bitr;
int bl = 0, br = 0;
int l2 = l, r2 = r;
while (l)
bitl.pb(l % 2), bl++, l >>= 1;
while (r)
bitr.pb(r % 2), br++, r >>= 1;
for (int i = bl + 1; i <= br; i++)
bitl.pb(0);
reverse(bitl.begin(), bitl.end());
reverse(bitr.begin(), bitr.end());
if (l2 == r2)
vec.pb(node(bitl, bitr));
else if (r2 - l2 == 1 && l2 % 2 == 0)
vec.pb(node{bitl, bitr});
else
wk(bitl, bitr);
int mxsuf = 0;
// for (auto x : vec)
// {
// for (auto u : x.l)
// cout << u;
// cout << " ";
// for (auto u : x.r)
// cout << u;
// cout << endl;
// }
for (auto x : vec)
{
int n = x.l.size();
vector<int> common;
int need = 0;
bool flag = 0;
for (int i = 0; i < n; i++)
if (x.l[i] == x.r[i])
{
if (x.l[i] == 1)
flag = 1;
if (flag)
common.pb(x.l[i]);
}
else
{
need = n - i;
break;
}
insert(common, need);
// for (auto x : common)
// cout << x;
// cout << " ";
// cout << "XX " << need << endl;
mxsuf = max(mxsuf, need);
}
for (int i = 1; i <= mxsuf; i++)
edge[nodenum + i].pb(P{nodenum + i + 1, 0}), edge[nodenum + i].pb(P{nodenum + i + 1, 1});
endpos = nodenum + mxsuf + 1;
dfs(1);
// cout << nodenum << " " << endpos << endl;
// for (int i = 1; i < nodenum; i++)
//{
// cout << trie[i][0] << " " << trie[i][1] << endl;
// }
cout << endpos << endl;
for (int i = 1; i <= endpos; i++)
{
cout << edge[i].size() << " ";
for (auto x : edge[i])
cout << x.fi << " " << x.se << " ";
cout << endl;
}
__();
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3644kb
input:
5 7
output:
5 1 2 1 2 3 0 4 1 1 5 1 2 5 0 5 1 0
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
10 27
output:
9 1 2 1 4 3 0 4 1 6 0 7 1 1 8 1 1 5 0 2 8 0 8 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 0
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
5 13
output:
7 1 2 1 4 3 0 4 1 5 0 6 1 1 7 1 1 6 0 2 6 0 6 1 2 7 0 7 1 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1 1000000
output:
39 20 2 1 39 1 38 1 37 1 36 1 35 1 34 1 33 1 32 1 31 1 30 1 29 1 28 1 27 1 26 1 25 1 24 1 23 1 22 1 21 1 2 3 1 21 0 2 4 1 22 0 2 5 1 23 0 1 6 0 2 7 1 25 0 1 8 0 1 9 0 1 10 0 1 11 0 2 12 1 30 0 1 13 0 1 14 0 2 15 1 33 0 1 16 0 1 17 0 1 18 0 1 19 0 1 20 0 1 39 0 2 22 0 22 1 2 23 0...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
7 9
output:
6 1 2 1 2 4 0 3 1 1 6 1 1 5 0 2 6 0 6 1 0
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
3 7
output:
4 1 2 1 3 3 0 4 1 3 1 2 4 0 4 1 0
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1 5
output:
4 3 2 1 4 1 3 1 1 3 0 2 4 0 4 1 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
1 4
output:
5 3 2 1 5 1 4 1 1 3 0 1 5 0 2 5 0 5 1 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
8 9
output:
5 1 2 1 1 3 0 1 4 0 2 5 0 5 1 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
7 51
output:
10 3 2 1 7 1 6 1 2 3 1 6 0 2 4 0 10 1 1 5 0 2 9 0 9 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 0
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
51 79
output:
14 1 2 1 2 7 0 3 1 2 4 0 11 1 2 5 0 12 1 1 6 1 1 14 1 1 8 0 2 9 1 11 0 2 10 1 12 0 2 13 0 13 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 0
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
92 99
output:
12 1 2 1 2 3 0 7 1 1 4 1 1 5 1 1 6 1 2 11 0 11 1 1 8 0 1 9 0 1 10 0 2 11 0 11 1 2 12 0 12 1 0
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
27 36
output:
12 1 2 1 2 6 0 3 1 2 4 0 10 1 1 5 1 1 12 1 1 7 0 2 8 1 10 0 1 9 0 1 12 0 2 11 0 11 1 2 12 0 12 1 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
55 84
output:
16 1 2 1 2 7 0 3 1 2 4 0 13 1 1 5 1 1 6 1 1 16 1 2 8 1 12 0 1 9 0 2 10 1 14 0 1 11 0 1 16 0 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
297208 929600
output:
55 1 2 1 4 3 0 19 1 37 0 38 1 2 4 0 39 1 1 5 1 2 6 0 41 1 2 7 0 42 1 2 8 0 43 1 1 9 1 2 10 0 45 1 2 11 0 46 1 2 12 0 47 1 1 13 1 1 14 1 1 15 1 1 16 1 1 17 1 2 18 0 53 1 2 54 0 54 1 2 20 1 38 0 1 21 0 1 22 0 1 23 0 2 24 1 42 0 1 25 0 2 26 1 44 0 2 27 1 45 0 2 28 1 46 0 2 29...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
45728 589156
output:
51 4 2 1 35 1 34 1 33 1 2 3 0 37 1 2 16 0 4 1 1 5 1 2 6 0 40 1 2 7 0 41 1 1 8 1 2 9 0 43 1 1 10 1 2 11 0 45 1 1 12 1 2 13 0 47 1 2 14 0 48 1 2 15 0 49 1 2 50 0 50 1 1 17 0 2 18 1 36 0 2 19 1 37 0 2 20 1 38 0 2 21 1 39 0 2 22 1 40 0 2 23 1 41 0 1 24 0 2 25 1 43 0 1 26 0 2 27 ...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
129152 138000
output:
45 1 2 1 2 17 0 3 1 1 4 1 1 5 1 1 6 1 1 7 1 2 8 0 35 1 2 9 0 36 1 2 10 0 37 1 1 11 1 2 12 0 39 1 2 13 0 40 1 2 14 0 41 1 2 15 0 42 1 2 16 0 43 1 2 44 0 44 1 1 18 0 1 19 0 1 20 0 2 21 1 33 0 2 22 1 34 0 1 23 0 2 24 1 36 0 2 25 1 37 0 1 26 0 1 27 0 1 28 0 2 29 1 41 0 1 30 0...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
245280 654141
output:
53 2 2 1 35 1 2 18 0 3 1 1 4 1 2 5 0 39 1 1 6 1 1 7 1 1 8 1 1 9 1 1 10 1 2 11 0 45 1 2 12 0 46 1 2 13 0 47 1 1 14 1 2 15 0 49 1 2 16 0 50 1 2 17 0 51 1 2 52 0 52 1 1 19 0 2 20 1 37 0 2 21 1 38 0 2 22 1 39 0 2 23 1 40 0 2 24 1 41 0 2 25 1 42 0 1 26 0 2 27 1 44 0 2 28 1 45 0 ...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
202985 296000
output:
51 1 2 1 2 19 0 3 1 2 4 0 36 1 2 5 0 37 1 2 6 0 38 1 1 7 1 1 8 1 2 9 0 41 1 2 10 0 42 1 2 11 0 43 1 1 12 1 1 13 1 1 14 1 2 15 0 47 1 1 16 1 2 17 0 49 1 2 18 0 50 1 1 51 1 1 20 0 2 21 1 36 0 1 22 0 1 23 0 1 24 0 1 25 0 2 26 1 41 0 1 27 0 1 28 0 1 29 0 2 30 1 45 0 1 31 0 ...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
438671 951305
output:
54 1 2 1 2 3 1 36 0 4 4 0 20 1 37 0 38 1 1 5 1 2 6 0 40 1 1 7 1 1 8 1 2 9 0 43 1 2 10 0 44 1 2 11 0 45 1 1 12 1 1 13 1 2 14 0 48 1 2 15 0 49 1 2 16 0 50 1 1 17 1 1 18 1 1 19 1 1 54 1 1 21 0 2 22 1 39 0 1 23 0 1 24 0 1 25 0 1 26 0 2 27 1 44 0 1 28 0 1 29 0 1 30 0 1 31 0 ...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
425249 739633
output:
54 1 2 1 2 20 0 3 1 2 4 0 38 1 2 5 0 39 1 1 6 1 1 7 1 1 8 1 1 9 1 1 10 1 2 11 0 45 1 1 12 1 2 13 0 47 1 2 14 0 48 1 1 15 1 2 16 0 50 1 2 17 0 51 1 2 18 0 52 1 2 19 0 53 1 1 54 1 2 21 1 37 0 2 22 1 38 0 1 23 0 2 24 1 40 0 1 25 0 1 26 0 2 27 1 43 0 1 28 0 1 29 0 2 30 1 46 0...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
551207 961718
output:
56 1 2 1 2 3 0 21 1 2 4 0 39 1 2 5 0 40 1 2 6 0 41 1 1 7 1 1 8 1 2 9 0 44 1 1 10 1 2 11 0 46 1 2 12 0 47 1 1 13 1 2 14 0 49 1 2 15 0 50 1 1 16 1 2 17 0 52 1 2 18 0 53 1 1 19 1 1 20 1 1 56 1 2 22 1 39 0 1 23 0 2 24 1 41 0 1 25 0 2 26 1 43 0 1 27 0 2 28 1 45 0 2 29 1 46 0 1...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
114691 598186
output:
54 3 2 1 37 1 36 1 2 18 0 3 1 1 4 1 2 5 0 41 1 2 6 0 42 1 2 7 0 43 1 2 8 0 44 1 2 9 0 45 1 2 10 0 46 1 2 11 0 47 1 2 12 0 48 1 2 13 0 49 1 2 14 0 50 1 2 15 0 51 1 2 16 0 52 1 1 17 1 1 54 1 1 19 0 2 20 1 38 0 1 21 0 1 22 0 2 23 1 41 0 1 24 0 1 25 0 1 26 0 1 27 0 1 28 0 2 29...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
234654 253129
output:
44 1 2 1 1 3 1 1 4 1 2 5 0 18 1 2 6 0 31 1 1 7 1 2 8 0 33 1 1 9 1 2 10 0 35 1 2 11 0 36 1 1 12 1 2 13 0 38 1 2 14 0 39 1 1 15 1 1 16 1 1 17 1 1 43 1 1 19 0 2 20 1 32 0 2 21 1 33 0 2 22 1 34 0 1 23 0 1 24 0 2 25 1 37 0 2 26 1 38 0 1 27 0 1 28 0 2 29 1 41 0 1 30 0 1 43 0 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
554090 608599
output:
50 1 2 1 1 3 0 1 4 0 2 5 0 20 1 2 6 0 35 1 1 7 1 1 8 1 1 9 1 2 10 0 39 1 1 11 1 2 12 0 41 1 2 13 0 42 1 2 14 0 43 1 1 15 1 1 16 1 2 17 0 46 1 1 18 1 2 19 0 48 1 1 49 1 1 21 0 2 22 1 36 0 1 23 0 1 24 0 2 25 1 39 0 1 26 0 1 27 0 2 28 1 42 0 1 29 0 2 30 1 44 0 1 31 0 2 32 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed