QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#684686 | #9519. Build a Computer | MiniLong | AC ✓ | 0ms | 3696kb | C++20 | 3.6kb | 2024-10-28 15:12:02 | 2024-10-28 15:12:04 |
Judging History
answer
#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; ++i)
#define _req(i, x, y) for(int i = x; i >= y; --i)
#define _rev(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define mst(f, i) memset(f, i, sizeof f)
using namespace std;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
typedef pair<int, int> PII;
namespace fastio{
#ifdef ONLINE_JUDGE
char ibuf[1 << 20],*p1 = ibuf, *p2 = ibuf;
#define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++
#else
#define get() getchar()
#endif
template<typename T> inline void read(T &t){
T x = 0, f = 1;
char c = getchar();
while(!isdigit(c)){
if(c == '-') f = -f;
c = getchar();
}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
t = x * f;
}
template<typename T, typename ... Args> inline void read(T &t, Args&... args){
read(t);
read(args...);
}
template<typename T> void write(T t){
if(t < 0) putchar('-'), t = -t;
if(t >= 10) write(t / 10);
putchar(t % 10 + '0');
}
template<typename T, typename ... Args> void write(T t, Args... args){
write(t), putchar(' '), write(args...);
}
template<typename T> void writeln(T t){
write(t);
puts("");
}
template<typename T> void writes(T t){
write(t), putchar(' ');
}
#undef get
};
using namespace fastio;
#define multitest() int T; read(T); _rep(tCase, 1, T)
namespace Calculation{
const ll mod = 998244353;
ll ksm(ll p, ll h){ll base = p % mod, res = 1; while(h){if(h & 1ll) res = res * base % mod; base = base * base % mod, h >>= 1ll;} return res;}
void dec(ll &x, ll y){x = ((x - y) % mod + mod) % mod;}
void add(ll &x, ll y){x = (x + y) % mod;}
void mul(ll &x, ll y){x = x * y % mod;}
ll sub(ll x, ll y){return ((x - y) % mod + mod) % mod;}
ll pls(ll x, ll y){return ((x + y) % mod + mod) % mod;}
ll mult(ll x, ll y){return x * y % mod;}
}
using namespace Calculation;
const int N = 1005;
int s, t, L, R, maxn, id, a[N];
vector<PII> G[N];
void link(int u, int v, int w){
G[u].pb({v, w});
}
int get(int x){
if(x > maxn){
_rep(i, maxn + 1, x){
a[i] = ++id, link(a[i], a[i - 1], 0), link(a[i], a[i - 1], 1);
}
maxn = x;
}
return a[x];
}
int dfs(int u, int L, int R, int lim, bool flag){
if(u == -1) return t;
if(!lim) return get(u + 1);
int cl = L >> u & 1, cr = R >> u & 1;
int x = 0;
_rep(i, 0, 1){
if((lim & 1) && i < cl) continue;
if((lim & 2) && i > cr) continue;
int nlim = (lim & (i == cl)) | (lim & ((i == cr) << 1));
bool nflag = flag & (!i);
if(flag){
// if(u == 4 && i == 0) debug("fff nlim:%d nflag:%d\n", nlim, nflag);
if(nflag) dfs(u - 1, L, R, nlim, nflag);
else link(s, dfs(u - 1, L, R, nlim, nflag), 1);
}else{
if(!x) x = ++id;
int v = dfs(u - 1, L, R, nlim, nflag);
if(v) link(x, v, i);
}
}
// debug("dfs u:%d lim:%d flag:%d x:%d\n", u, lim, flag, x);
return x;
}
int main(){
s = ++id, t = ++id, a[0] = t;
read(L, R);
dfs(max(__lg(L), __lg(R)), L, R, 3, 1);
writeln(id);
_rep(i, 1, id){
writes(G[i].size());
for(auto &j : G[i]) write(j.fi, j.se), putchar(' ');
puts("");
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
5 7
output:
5 1 3 1 0 2 4 0 5 1 1 2 1 2 2 0 2 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
10 27
output:
12 2 3 1 8 1 0 2 4 0 7 1 1 5 1 2 2 0 2 1 2 2 0 2 1 2 6 0 6 1 2 9 0 10 1 2 7 0 7 1 1 11 0 2 6 0 12 1 2 2 0 2 1
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
5 13
output:
9 2 3 1 6 1 0 2 4 0 5 1 1 2 1 2 2 0 2 1 2 7 0 8 1 2 5 0 5 1 1 9 0 2 2 0 2 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1 1000000
output:
39 20 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 17 1 18 1 19 1 20 1 21 1 0 2 2 0 2 1 2 3 0 3 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...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
7 9
output:
7 2 3 1 5 1 0 1 4 1 1 2 1 1 6 0 1 7 0 2 2 0 2 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
3 7
output:
6 2 3 1 4 1 0 1 2 1 2 5 0 6 1 2 2 0 2 1 2 2 0 2 1
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
1 5
output:
5 3 2 1 3 1 4 1 0 2 2 0 2 1 1 5 0 2 2 0 2 1
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1 4
output:
5 3 2 1 3 1 4 1 0 2 2 0 2 1 1 5 0 1 2 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
8 9
output:
5 1 3 1 0 1 4 0 1 5 0 2 2 0 2 1
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
7 51
output:
13 4 3 1 7 1 8 1 9 1 0 1 4 1 1 2 1 2 2 0 2 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 10 1 1 11 0 1 12 0 2 5 0 13 1 2 2 0 2 1
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
51 79
output:
16 2 3 1 11 1 0 1 4 1 2 5 0 10 1 2 6 0 9 1 1 7 1 1 2 1 2 2 0 2 1 2 8 0 8 1 2 9 0 9 1 1 12 0 1 13 0 2 10 0 14 1 2 9 0 15 1 2 8 0 16 1 2 2 0 2 1
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
92 99
output:
14 1 3 1 0 2 4 0 10 1 1 5 1 1 6 1 1 7 1 2 8 0 9 1 2 2 0 2 1 2 2 0 2 1 1 11 0 1 12 0 1 13 0 2 9 0 14 1 2 2 0 2 1
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
27 36
output:
13 2 3 1 9 1 0 1 4 1 2 5 0 8 1 1 6 1 1 2 1 2 2 0 2 1 2 7 0 7 1 1 10 0 1 11 0 2 8 0 12 1 1 13 0 1 2 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
55 84
output:
17 2 3 1 11 1 0 1 4 1 2 5 0 10 1 1 6 1 1 7 1 1 2 1 2 2 0 2 1 2 8 0 8 1 2 9 0 9 1 1 12 0 2 13 0 14 1 2 10 0 10 1 1 15 0 2 9 0 16 1 1 17 0 1 2 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
297208 929600
output:
57 2 3 1 38 1 0 2 4 0 37 1 2 5 0 36 1 1 6 1 2 7 0 34 1 2 8 0 33 1 2 9 0 32 1 1 10 1 2 11 0 30 1 2 12 0 29 1 2 13 0 28 1 1 14 1 1 15 1 1 16 1 1 17 1 1 18 1 2 19 0 22 1 2 20 0 21 1 2 2 0 2 1 2 2 0 2 1 2 21 0 21 1 2 22 0 22 1 2 23 0 23 1 2 24 0 24 1 2 25 0 25 1 2 26 0 26 1 2 ...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
45728 589156
output:
54 5 3 1 33 1 34 1 35 1 36 1 0 2 4 0 31 1 1 5 1 1 6 1 2 7 0 28 1 2 8 0 27 1 1 9 1 2 10 0 25 1 1 11 1 2 12 0 23 1 1 13 1 2 14 0 21 1 2 15 0 20 1 2 16 0 19 1 2 17 0 18 1 2 2 0 2 1 2 2 0 2 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 21 0 21 1 2 22 0 22 1 2 23 0 23 1 2 24 0 24 1 2 2...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
129152 138000
output:
47 2 3 1 29 1 0 1 4 1 1 5 1 1 6 1 1 7 1 1 8 1 2 9 0 28 1 2 10 0 27 1 2 11 0 26 1 1 12 1 2 13 0 24 1 2 14 0 23 1 2 15 0 22 1 2 16 0 21 1 2 17 0 20 1 2 18 0 19 1 2 2 0 2 1 2 2 0 2 1 2 19 0 19 1 2 20 0 20 1 2 21 0 21 1 2 22 0 22 1 2 23 0 23 1 2 24 0 24 1 2 25 0 25 1 2 26 0 26 ...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
245280 654141
output:
56 3 3 1 37 1 38 1 0 1 4 1 1 5 1 2 6 0 33 1 1 7 1 1 8 1 1 9 1 1 10 1 1 11 1 2 12 0 27 1 2 13 0 26 1 2 14 0 25 1 1 15 1 2 16 0 23 1 2 17 0 22 1 2 18 0 21 1 2 19 0 20 1 2 2 0 2 1 2 2 0 2 1 2 20 0 20 1 2 21 0 21 1 2 22 0 22 1 2 23 0 23 1 2 24 0 24 1 2 25 0 25 1 2 26 0 26 1 2 ...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
202985 296000
output:
52 2 3 1 35 1 0 1 4 1 2 5 0 34 1 2 6 0 33 1 2 7 0 32 1 1 8 1 1 9 1 2 10 0 29 1 2 11 0 28 1 2 12 0 27 1 1 13 1 1 14 1 1 15 1 2 16 0 23 1 1 17 1 2 18 0 21 1 2 19 0 20 1 1 2 1 2 2 0 2 1 2 20 0 20 1 2 21 0 21 1 2 22 0 22 1 2 23 0 23 1 2 24 0 24 1 2 25 0 25 1 2 26 0 26 1 2 27 0...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
438671 951305
output:
57 2 3 1 37 1 0 1 4 1 2 5 0 36 1 1 6 1 2 7 0 34 1 1 8 1 1 9 1 2 10 0 31 1 2 11 0 30 1 2 12 0 29 1 1 13 1 1 14 1 2 15 0 26 1 2 16 0 25 1 2 17 0 24 1 1 18 1 1 19 1 1 20 1 1 2 1 2 2 0 2 1 2 21 0 21 1 2 22 0 22 1 2 23 0 23 1 2 24 0 24 1 2 25 0 25 1 2 26 0 26 1 2 27 0 27 1 2 2...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
425249 739633
output:
56 2 3 1 37 1 0 1 4 1 2 5 0 36 1 2 6 0 35 1 1 7 1 1 8 1 1 9 1 1 10 1 1 11 1 2 12 0 29 1 1 13 1 2 14 0 27 1 2 15 0 26 1 1 16 1 2 17 0 24 1 2 18 0 23 1 2 19 0 22 1 2 20 0 21 1 1 2 1 2 2 0 2 1 2 21 0 21 1 2 22 0 22 1 2 23 0 23 1 2 24 0 24 1 2 25 0 25 1 2 26 0 26 1 2 27 0 27 1...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
551207 961718
output:
56 1 3 1 0 2 4 0 39 1 2 5 0 38 1 2 6 0 37 1 2 7 0 36 1 1 8 1 1 9 1 2 10 0 33 1 1 11 1 2 12 0 31 1 2 13 0 30 1 1 14 1 2 15 0 28 1 2 16 0 27 1 1 17 1 2 18 0 25 1 2 19 0 24 1 1 20 1 1 21 1 1 2 1 2 2 0 2 1 2 22 0 22 1 2 23 0 23 1 2 24 0 24 1 2 25 0 25 1 2 26 0 26 1 2 27 0 27 1...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
114691 598186
output:
55 4 3 1 35 1 36 1 37 1 0 1 4 1 1 5 1 2 6 0 31 1 2 7 0 30 1 2 8 0 29 1 2 9 0 28 1 2 10 0 27 1 2 11 0 26 1 2 12 0 25 1 2 13 0 24 1 2 14 0 23 1 2 15 0 22 1 2 16 0 21 1 2 17 0 20 1 1 18 1 1 2 1 2 2 0 2 1 2 19 0 19 1 2 20 0 20 1 2 21 0 21 1 2 22 0 22 1 2 23 0 23 1 2 24 0 24 1 2 ...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
234654 253129
output:
46 1 3 1 0 1 4 1 1 5 1 2 6 0 33 1 2 7 0 32 1 1 8 1 2 9 0 30 1 1 10 1 2 11 0 28 1 2 12 0 27 1 1 13 1 2 14 0 25 1 2 15 0 24 1 1 16 1 1 17 1 1 18 1 1 19 1 2 2 0 2 1 2 2 0 2 1 2 20 0 20 1 2 21 0 21 1 2 22 0 22 1 2 23 0 23 1 2 24 0 24 1 2 25 0 25 1 2 26 0 26 1 2 27 0 27 1 2 28...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
554090 608599
output:
52 1 3 1 0 1 4 0 1 5 0 2 6 0 37 1 2 7 0 36 1 1 8 1 1 9 1 1 10 1 2 11 0 32 1 1 12 1 2 13 0 30 1 2 14 0 29 1 2 15 0 28 1 1 16 1 1 17 1 2 18 0 25 1 1 19 1 2 20 0 23 1 1 21 1 2 2 0 2 1 2 2 0 2 1 2 22 0 22 1 2 23 0 23 1 2 24 0 24 1 2 25 0 25 1 2 26 0 26 1 2 27 0 27 1 2 28 0 28...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed