QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#680900 | #9519. Build a Computer | ucup-team2796# | AC ✓ | 1ms | 3852kb | C++17 | 5.8kb | 2024-10-26 23:23:18 | 2024-10-26 23:23:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define rrep(i, a, b) for (ll i = (ll)(b)-1; i >= (ll)(a); i--)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;
template <typename T> inline bool chmax(T &a, T b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <typename T> inline bool chmin(T &a, T b) {
if (a > b) {
a = b;
return 1;
}
return 0;
}
template <typename T, typename U> T ceil(T x, U y) {
assert(y != 0);
if (y < 0)
x = -x, y = -y;
return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U> T floor(T x, U y) {
assert(y != 0);
if (y < 0)
x = -x, y = -y;
return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T> int popcnt(T x) {
return __builtin_popcountll(x);
}
template <typename T> int topbit(T x) {
return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
template <typename T> int lowbit(T x) {
return (x == 0 ? -1 : __builtin_ctzll(x));
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << "P(" << p.first << ", " << p.second << ")";
return os;
}
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {
os << "{";
for (int i = 0; i < vec.size(); i++) {
os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
}
os << "}";
return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
os << "{";
for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
os << "(" << itr->first << ", " << itr->second << ")";
itr++;
if (itr != map_var.end())
os << ", ";
itr--;
}
os << "}";
return os;
}
template <typename T> ostream &operator<<(ostream &os, const set<T> &set_var) {
os << "{";
for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
os << *itr;
++itr;
if (itr != set_var.end())
os << ", ";
itr--;
}
os << "}";
return os;
}
#ifdef LOCAL
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define show(...) true
#endif
template <typename T> void _show(int i, T name) {
cerr << '\n';
}
template <typename T1, typename T2, typename... T3>
void _show(int i, const T1 &a, const T2 &b, const T3 &...c) {
for (; a[i] != ',' && a[i] != '\0'; i++)
cerr << a[i];
cerr << ":" << b << " ";
_show(i + 1, a, c...);
}
/**
* @brief template
*/
vector<int> Dist(vector<vector<int>> G, int S) {
int N = G.size();
vector<int> Ret(N,inf);
Ret[S] = 0;
queue<int> Q;
Q.push(S);
while(!Q.empty()) {
int P = Q.front();
Q.pop();
for (int NP : G[P]) {
if (chmin(Ret[NP],Ret[P]+1)) {
Q.push(NP);
}
}
}
return Ret;
}
vector<int> toBinary(int X) {
vector<int> Ret;
while(X > 0) Ret.push_back(X % 2), X /= 2;
reverse(Ret.begin(), Ret.end());
return Ret;
}
vector<int> PopFront(vector<int> A) {
vector<int> Ret;
rep(i,1,A.size()) Ret.push_back(A[i]);
return Ret;
}
int main() {
int MAXS = 100;
int Start = 0, End = 99;
int XL, XR;
cin >> XL >> XR;
XL--, XR++;
auto L = toBinary(XL), R = toBinary(XR);
vector<vector<pair<int,int>>> G(MAXS);
auto AllBit = [&](int i) -> int {
return End - i;
};
rep(i,0,20) {
G[AllBit(i+1)].push_back({AllBit(i),0});
G[AllBit(i+1)].push_back({AllBit(i),1});
}
if (L.size() == R.size()) {
while(!L.empty()) {
if (L[0] != R[0]) break;
G[Start].push_back({Start+1,L[0]});
Start++;
L = PopFront(L);
R = PopFront(R);
}
}
else {
rep(i,L.size(),R.size() - 1) G[Start].push_back({AllBit(i),1});
}
int LS = 30, RS = 55;
rep(i,0,L.size()) {
if (i == 0) G[Start].push_back({LS,L[i]});
else {
G[LS+i-1].push_back({LS+i,L[i]});
if (L[i] == 0) G[LS+i-1].push_back({AllBit(L.size() - 1 - i), 1});
}
}
rep(i,0,R.size()) {
if (i == 0) G[Start].push_back({RS,R[i]});
else {
G[RS+i-1].push_back({RS+i,R[i]});
if (R[i] == 1) G[RS+i-1].push_back({AllBit(R.size() - 1 - i), 0});
}
}
vector<vector<int>> H(MAXS), RH(MAXS);
rep(i,0,MAXS) {
for (auto P : G[i]) {
H[i].push_back(P.first);
RH[P.first].push_back(i);
}
}
Start = 0;
auto DH = Dist(H,Start), DRH = Dist(RH,End);
vector<pair<int,int>> V;
rep(i,0,MAXS) {
if (DH[i] < inf && DRH[i] < inf) V.push_back({DH[i],i});
}
sort(ALL(V));
vector<int> ID(MAXS,-1);
rep(i,0,V.size()) ID[V[i].second] = i;
cout << V.size() << endl;
for (auto P : V) {
int i = P.second;
vector<pair<int,int>> ANS;
for (auto E : G[i]) {
if (ID[E.first] == -1) continue;
ANS.push_back({ID[E.first] + 1,E.second});
}
cout << ANS.size();
rep(j,0,ANS.size()) {
cout << ' ' << ANS[j].first << ' ' << ANS[j].second;
}
cout << endl;
}
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
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: 3644kb
input:
10 27
output:
9 2 2 1 3 1 2 4 0 7 1 2 5 1 6 0 1 8 1 1 7 0 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: 3812kb
input:
5 13
output:
8 2 2 1 3 1 2 4 0 7 1 2 5 1 6 0 1 8 1 1 7 0 2 7 0 7 1 2 8 0 8 1 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
1 1000000
output:
39 20 21 1 20 1 19 1 18 1 17 1 16 1 15 1 14 1 13 1 12 1 11 1 10 1 9 1 8 1 7 1 6 1 5 1 4 1 3 1 2 1 2 22 1 3 0 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...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
7 9
output:
7 2 2 1 3 1 1 4 1 1 5 0 1 7 1 1 6 0 2 7 0 7 1 0
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
3 7
output:
5 2 3 1 2 1 1 5 1 2 4 0 4 1 2 5 0 5 1 0
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
1 5
output:
4 3 4 1 3 1 2 1 1 3 0 2 4 0 4 1 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
1 4
output:
5 3 4 1 3 1 2 1 1 5 0 2 4 0 4 1 0 1 4 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3608kb
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: 3588kb
input:
7 51
output:
11 4 5 1 4 1 2 1 3 1 1 6 1 2 7 1 4 0 2 5 0 5 1 2 8 0 8 1 1 11 1 1 9 0 2 10 0 10 1 1 8 0 2 11 0 11 1 0
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
51 79
output:
13 2 2 1 3 1 1 4 1 1 5 0 2 6 0 8 1 1 7 0 2 9 0 10 1 2 8 0 8 1 2 10 0 10 1 1 11 1 2 12 0 12 1 1 13 1 2 13 0 13 1 0
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
92 99
output:
11 1 2 1 2 3 0 4 1 1 5 1 1 6 0 1 7 1 1 8 0 1 9 1 1 9 0 2 10 0 10 1 2 11 0 11 1 0
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
27 36
output:
13 2 2 1 3 1 1 4 1 1 5 0 2 6 0 8 1 1 7 0 1 9 1 2 10 1 8 0 2 11 0 11 1 1 13 1 1 12 0 2 13 0 13 1 1 13 0 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
55 84
output:
17 2 2 1 3 1 1 4 1 1 5 0 2 6 0 9 1 2 7 1 8 0 1 10 1 1 11 0 2 9 0 9 1 2 12 0 12 1 1 13 1 2 14 1 12 0 2 15 0 15 1 1 17 1 1 16 0 2 17 0 17 1 1 17 0 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
297208 929600
output:
54 2 2 1 3 1 2 4 0 7 1 2 5 1 6 0 2 8 0 10 1 2 9 1 7 0 2 7 0 7 1 2 10 0 10 1 1 11 1 1 12 0 2 13 0 13 1 2 14 0 16 1 1 15 0 2 16 0 16 1 2 17 0 19 1 1 18 0 2 19 0 19 1 2 20 0 22 1 2 21 1 19 0 2 22 0 22 1 1 23 1 1 24 0 2 25 0 25 1 2 26 0 28 1 2 27 1 25 0 2 28 0 28 1 2 29 0 31 1 2 30 1 28 0 2 31 0 31 1 2 ...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
45728 589156
output:
49 5 6 1 5 1 4 1 2 1 3 1 2 7 0 10 1 1 8 0 2 5 0 5 1 2 6 0 6 1 2 9 0 9 1 1 11 1 1 12 0 2 10 0 10 1 2 13 0 13 1 1 14 1 1 15 0 2 16 0 16 1 2 17 0 19 1 2 18 1 9 0 2 19 0 19 1 2 20 0 22 1 2 21 1 10 0 2 22 0 22 1 1 23 1 2 24 1 13 0 2 25 0 25 1 2 26 0 28 1 2 27 1 16 0 2 28 0 28 1 1 29 1 2 30 1 19 0 2 31 0 ...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
129152 138000
output:
40 2 2 1 3 1 1 4 1 1 5 0 1 6 1 1 7 0 1 8 1 1 9 0 1 10 1 1 11 0 1 12 1 2 13 1 14 0 2 15 0 18 1 2 16 1 17 0 2 17 0 17 1 2 19 0 21 1 1 20 0 2 18 0 18 1 2 21 0 21 1 2 22 0 24 1 2 23 1 21 0 2 24 0 24 1 1 26 1 2 25 1 24 0 2 26 0 26 1 1 27 0 2 28 0 28 1 1 29 0 2 30 0 30 1 1 31 0 2 32 0 32 1 2 33 1 32 0 2 3...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
245280 654141
output:
50 3 4 1 2 1 3 1 1 5 1 1 6 0 2 7 0 7 1 1 8 1 1 9 0 2 10 0 10 1 2 11 0 14 1 2 12 1 10 0 2 13 0 13 1 1 15 1 2 16 1 13 0 2 14 0 14 1 2 17 0 17 1 1 18 1 2 19 1 14 0 2 20 0 20 1 1 21 1 2 22 1 17 0 2 23 0 23 1 1 24 1 2 25 1 20 0 2 26 0 26 1 1 27 1 2 28 1 23 0 2 29 0 29 1 2 30 0 32 1 1 31 0 2 32 0 32 1 2 3...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
202985 296000
output:
52 2 2 1 3 1 1 4 1 1 5 0 2 6 0 8 1 1 7 0 2 9 0 11 1 2 10 1 8 0 2 11 0 11 1 2 12 0 14 1 1 13 0 2 14 0 14 1 1 15 1 1 16 0 2 17 0 17 1 1 18 1 1 19 0 2 20 0 20 1 2 21 0 23 1 1 22 0 2 23 0 23 1 2 24 0 26 1 2 25 1 23 0 2 26 0 26 1 2 27 0 29 1 1 28 0 2 29 0 29 1 1 30 1 1 31 0 2 32 0 32 1 1 33 1 1 34 0 2 35...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
438671 951305
output:
56 2 2 1 3 1 1 4 1 2 5 1 6 0 2 7 0 10 1 2 8 1 9 0 2 9 0 9 1 1 11 1 1 12 0 2 10 0 10 1 2 13 0 13 1 2 14 0 16 1 2 15 1 13 0 2 16 0 16 1 1 17 1 1 18 0 2 19 0 19 1 1 20 1 1 21 0 2 22 0 22 1 2 23 0 25 1 1 24 0 2 25 0 25 1 2 26 0 28 1 1 27 0 2 28 0 28 1 2 29 0 31 1 2 30 1 28 0 2 31 0 31 1 1 32 1 1 33 0 2 ...
result:
ok ok
Test #22:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
425249 739633
output:
55 2 2 1 3 1 1 4 1 1 5 0 2 6 0 9 1 2 7 1 8 0 2 10 0 12 1 2 11 1 9 0 2 9 0 9 1 2 12 0 12 1 1 13 1 1 14 0 2 15 0 15 1 1 16 1 2 17 1 15 0 2 18 0 18 1 1 19 1 1 20 0 2 21 0 21 1 1 22 1 1 23 0 2 24 0 24 1 1 25 1 2 26 1 24 0 2 27 0 27 1 2 28 0 30 1 1 29 0 2 30 0 30 1 1 31 1 1 32 0 2 33 0 33 1 2 34 0 36 1 2...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
551207 961718
output:
56 1 2 1 2 3 0 4 1 2 5 0 7 1 2 6 1 7 0 2 8 0 10 1 1 9 0 2 10 0 10 1 2 11 0 13 1 2 12 1 13 0 2 13 0 13 1 1 14 1 1 15 0 2 16 0 16 1 1 17 1 2 18 1 19 0 2 19 0 19 1 2 20 0 22 1 1 21 0 2 22 0 22 1 1 23 1 2 24 1 25 0 2 25 0 25 1 2 26 0 28 1 2 27 1 28 0 2 28 0 28 1 2 29 0 31 1 1 30 0 2 31 0 31 1 1 32 1 1 3...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
114691 598186
output:
55 4 5 1 4 1 2 1 3 1 1 6 1 1 7 0 2 5 0 5 1 2 8 0 8 1 1 9 1 1 10 0 2 11 0 11 1 2 12 0 15 1 2 13 1 8 0 2 14 0 14 1 2 16 0 18 1 1 17 0 2 15 0 15 1 2 18 0 18 1 2 19 0 21 1 1 20 0 2 21 0 21 1 2 22 0 24 1 2 23 1 15 0 2 24 0 24 1 2 25 0 27 1 1 26 0 2 27 0 27 1 2 28 0 30 1 1 29 0 2 30 0 30 1 2 31 0 33 1 1 3...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
234654 253129
output:
44 1 2 1 1 3 1 1 4 1 2 5 0 6 1 2 7 0 9 1 1 8 0 1 10 1 2 11 1 12 0 2 12 0 12 1 2 13 0 15 1 2 14 1 15 0 2 15 0 15 1 1 16 1 2 17 1 18 0 2 18 0 18 1 2 19 0 21 1 1 20 0 2 21 0 21 1 2 22 0 24 1 1 23 0 2 24 0 24 1 1 25 1 2 26 1 27 0 2 27 0 27 1 2 28 0 30 1 2 29 1 30 0 2 30 0 30 1 2 31 0 33 1 1 32 0 2 33 0 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
554090 608599
output:
48 1 2 1 1 3 0 1 4 0 2 5 0 6 1 2 7 0 9 1 1 8 0 1 10 1 2 11 1 12 0 2 12 0 12 1 1 13 1 1 14 0 2 15 0 15 1 1 16 1 1 17 0 2 18 0 18 1 2 19 0 21 1 2 20 1 21 0 2 21 0 21 1 1 22 1 1 23 0 2 24 0 24 1 2 25 0 27 1 1 26 0 2 27 0 27 1 2 28 0 30 1 2 29 1 30 0 2 30 0 30 1 2 31 0 33 1 1 32 0 2 33 0 33 1 1 34 1 2 3...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed