QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#680300 | #9519. Build a Computer | ucup-team5351# | AC ✓ | 1ms | 4104kb | C++14 | 3.7kb | 2024-10-26 20:33:13 | 2024-10-26 20:33:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#define ALL(v) v.begin(),v.end()
#define For(i,_) for(int i=0,i##end=_;i<i##end;++i) // [0,_)
#define FOR(i,_,__) for(int i=_,i##end=__;i<i##end;++i) // [_,__)
#define Rep(i,_) for(int i=(_)-1;i>=0;--i) // [0,_)
#define REP(i,_,__) for(int i=(__)-1,i##end=_;i>=i##end;--i) // [_,__)
typedef long long ll;
typedef unsigned long long ull;
#define V vector
#define pb push_back
#define pf push_front
#define qb pop_back
#define qf pop_front
#define eb emplace_back
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
#define fi first
#define se second
const int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}},inf=0x3f3f3f3f,mod=1e9+7;
const ll infl=0x3f3f3f3f3f3f3f3fll;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
int init=[](){return cin.tie(nullptr)->sync_with_stdio(false),0;}();
int main(){
int t_case=1;
//scanf("%d",&t_case);
while(t_case--){
int L,R;
scanf("%d%d",&L,&R);
int x=1,y=1;
auto fuck=[&](auto &&self,int d,int l,int r)->void{
if(d==-1)return;
if(!l){
if(!r){
ckmax(y,d+1);
return;
}
if((r>>d&1)&&!(r&(r+1))){
ckmax(x,d+1);
return;
}
}
if((l>>d&1)==(r>>d&1)){
if(l>>d&1)self(self,d-1,l^(1<<d),r^(1<<d));
else self(self,d-1,l,r);
}
else self(self,d-1,l,(1<<d)-1),self(self,d-1,0,r^(1<<d));
};
fuck(fuck,19,L,R);
const int S=x+y-1;
int cnt=S;
V<V<pii>>to(100);
FOR(i,1,x)to[i].eb(i-1,0),to[i].eb(i-1,1);
FOR(i,x,S)to[i].eb(i>x?i-1:0,0);
auto dfs=[&](auto &&self,int d,int p,int l,int r)->int{
if(!l){
if(!r){
to[p].eb(d?x+d-1:0,0);
return p;
}
if((r>>d&1)&&!(r&(r+1))){
to[p].eb(d,0),to[p].eb(d,1);
return p;
}
}
if((l>>d&1)==(r>>d&1)){
if(l>>d&1)to[p].eb(d?self(self,d-1,cnt++,l^(1<<d),r^(1<<d)):0,1);
else{
if(p>S)to[p].eb(d?self(self,d-1,cnt++,l,r):0,0);
else self(self,d-1,S,l,r);
}
}
else{
if(p>S)to[p].eb(d?self(self,d-1,cnt++,l,(1<<d)-1):0,0);
else self(self,d-1,S,l,(1<<d)-1);
to[p].eb(d?self(self,d-1,cnt++,0,r^(1<<d)):0,1);
}
return p;
};
dfs(dfs,19,cnt++,L,R);
printf("%d\n",cnt);
For(i,cnt){
printf("%d",(int)to[i].size());
for(const pii &j:to[i])printf(" %d %d",j.fi+1,j.se);
putchar(10);
}
// V<int>deg(100);
// For(i,cnt)for(const pii &j:to[i])++deg[j.fi];
// assert(!deg[S]);
// V<set<int>>s(100);
// s[S].insert(0);
// queue<int>q;
// q.push(S);
// int retard=0;
// while(q.size()){
// int p=q.front();q.pop();
// ++retard;
// for(const pii &i:to[p]){
// for(int j:s[p])s[i.fi].insert(j<<1|i.se);
// if(!--deg[i.fi])q.push(i.fi);
// }
// }
// assert(retard==cnt);
// For(i,1<<20)assert(s[0].count(i)==(L<=i&&i<=R));
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4100kb
input:
5 7
output:
5 0 1 3 1 2 4 0 5 1 1 1 1 2 1 0 1 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 4048kb
input:
10 27
output:
12 0 2 1 0 1 1 2 2 0 2 1 2 5 1 9 1 2 6 0 8 1 1 7 1 2 1 0 1 1 2 2 0 2 1 2 10 0 11 1 2 3 0 3 1 1 12 0 2 2 0 2 1
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
5 13
output:
10 0 2 1 0 1 1 2 4 1 7 1 2 5 0 6 1 1 1 1 2 1 0 1 1 2 8 0 9 1 2 2 0 2 1 1 10 0 2 1 0 1 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
1 1000000
output:
62 0 2 1 0 1 1 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 1 1 0 1 19 0 1 20 0 1 21 0 1 22 0 20 1 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 ...
result:
ok ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 4104kb
input:
1 1
output:
2 0 1 1 1
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
7 9
output:
7 0 2 3 1 5 1 1 4 1 1 1 1 1 6 0 1 7 0 2 1 0 1 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
3 7
output:
5 0 2 1 0 1 1 2 4 1 5 1 1 1 1 2 2 0 2 1
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
1 5
output:
5 0 3 1 1 3 1 4 1 2 1 0 1 1 1 5 0 2 1 0 1 1
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
1 4
output:
5 0 1 1 0 3 1 1 4 1 5 1 2 1 0 1 1 1 2 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
8 9
output:
5 0 1 3 1 1 4 0 1 5 0 2 1 0 1 1
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
7 51
output:
14 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 4 6 1 8 1 9 1 10 1 1 7 1 1 1 1 2 3 0 3 1 2 4 0 4 1 2 11 0 12 1 2 4 0 4 1 1 13 0 1 14 0 2 2 0 2 1
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
51 79
output:
15 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 6 1 13 1 1 7 1 2 8 0 12 1 2 9 0 11 1 1 10 1 1 1 1 2 2 0 2 1 2 3 0 3 1 1 14 0 1 15 0 2 4 0 4 1
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 4080kb
input:
92 99
output:
12 0 2 1 0 1 1 1 4 1 2 5 0 9 1 1 6 1 1 7 1 1 8 1 2 2 0 2 1 1 10 0 1 11 0 1 12 0 2 2 0 2 1
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
27 36
output:
14 0 2 1 0 1 1 1 1 0 2 5 1 10 1 1 6 1 2 7 0 9 1 1 8 1 1 1 1 2 2 0 2 1 1 11 0 1 12 0 2 13 0 14 1 2 2 0 2 1 1 3 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 4076kb
input:
55 84
output:
19 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 1 1 0 2 7 1 13 1 1 8 1 2 9 0 12 1 1 10 1 1 11 1 1 1 1 2 3 0 3 1 1 14 0 2 15 0 16 1 2 4 0 4 1 1 17 0 2 18 0 19 1 2 2 0 2 1 1 5 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 4048kb
input:
297208 929600
output:
70 0 2 1 0 1 1 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 1 1 0 1 19 0 1 20 0 1 21 0 1 22 0 2 25 1 49 1 2 26 0 48 1 2 27 0 47 1 1 28 1 2 29 0 46 1 2 30 0 45 1 2 31 0 4...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
45728 589156
output:
67 0 2 1 0 1 1 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 1 1 0 5 21 1 37 1 38 1 39 1 40 1 2 22 0 36 1 1 23 1 1 24 1 2 25 0 35 1 2 26 0 34 1 1 27 1 2 28 0 33 1 1 29 1 ...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
129152 138000
output:
48 0 2 1 0 1 1 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 1 1 0 1 13 0 1 14 0 2 17 1 30 1 1 18 1 1 19 1 1 20 1 1 21 1 1 22 1 2 23 0 29 1 2 24 0 28 1 2 25 0 27 1 1 26 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 1 31 0 1 32 0 1 33 0 1 34 0 2...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
245280 654141
output:
68 0 2 1 0 1 1 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 3 20 1 37 1 38 1 1 21 1 1 22 1 2 23 0 36 1 1 24 1 1 25 1 1 26 1 1 27 1 1 28 1 2 29 0 35 1 2 30 0 34 1 2 31 0 ...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
202985 296000
output:
63 0 2 1 0 1 1 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 1 1 0 1 16 0 1 17 0 1 18 0 1 19 0 2 22 1 48 1 1 23 1 2 24 0 47 1 2 25 0 46 1 2 26 0 45 1 1 27 1 1 28 1 2 29 0 44 1 2 30 0 43 1 2 31 0 42 1 1 32 1...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
438671 951305
output:
69 0 2 1 0 1 1 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 20 1 46 1 1 21 1 2 22 0 45 1 1 23 1 2 24 0 44 1 1 25 1 1 26 1 2 27 0 43 1 2 28 0 42 1 2 29 0 41 1 1 30 1 1 ...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
425249 739633
output:
71 0 2 1 0 1 1 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 19 1 46 1 1 20 1 2 21 0 45 1 2 22 0 44 1 1 23 1 1 24 1 1 25 1 1 26 1 1 27 1 2 28 0 43 1 1 29 1 2 30 0 42 1 2 31 0 41 1 ...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
551207 961718
output:
75 0 2 1 0 1 1 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 1 19 1 2 20 0 48 1 2 21 0 47 1 2 22 0 46 1 2 23 0 45 1 1 24 1 1 25 1 2 26 0 44 1 1 27 1 2 28 0 43 1 2 29 0 42 1 1 30 1 2 ...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
114691 598186
output:
74 0 2 1 0 1 1 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 4 20 1 48 1 49 1 50 1 1 21 1 1 22 1 2 23 0 47 1 2 24 0 46 1 2 25 0 45 1 2 26 0 44 1 2 27 0 43 1 2 28 0 42 1 2...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
234654 253129
output:
57 0 2 1 0 1 1 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 1 15 1 1 16 1 1 17 1 2 18 0 38 1 2 19 0 37 1 1 20 1 2 21 0 36 1 1 22 1 2 23 0 35 1 2 24 0 34 1 1 25 1 2 26 0 33 1 2 27 0 32 1 1 28 1 1 29 1 1 30 1 1 31 1 2 1 0 1 1 2 5 0...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 4048kb
input:
554090 608599
output:
61 0 2 1 0 1 1 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 1 17 1 1 18 0 1 19 0 2 20 0 43 1 2 21 0 42 1 1 22 1 1 23 1 1 24 1 2 25 0 41 1 1 26 1 2 27 0 40 1 2 28 0 39 1 2 29 0 38 1 1 30 1 1 31 1 2 32 0 37 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed