QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #684368 | #9519. Build a Computer | Tggdb | AC ✓ | 368ms | 56768kb | C++20 | 9.2kb | 2024-10-28 12:56:55 | 2024-10-28 12:56:57 |
Judging History
answer
#include<bits/stdc++.h>
#define inf 0X7fffffff
using namespace std;
const int N=2e6+9;
int read(int &x){
int dat=0,oko=1;char chc=getchar();
while(chc<'0'||chc>'9'){if(chc=='-')oko=-1;chc=getchar();}
while(chc>='0'&&chc<='9'){dat=dat*10+chc-'0';chc=getchar();}
x=dat*oko;return x;
}int L,R,st[31],tot,p1,p2,ll,rr;
map<int,int>lg,mp;
int cnt,head[N],nxt[N<<1],to[N<<1],val[N<<1],dig[N];
void link(int f,int t,int v){
nxt[++cnt]=head[f],head[f]=cnt;
to[cnt]=t,val[cnt]=v,dig[f]++;
}int lowbit(int x){return x&(-x);}
int maxbit(int x){
while(x!=lowbit(x)){
x-=lowbit(x);
}return x;
}void dfs(int x,int num){
if(x==1){
if(num<ll||num>rr){
printf("error %d\n",num);
}mp[num]++;
return;
}
for(int i=head[x];i;i=nxt[i]){
dfs(to[i],num<<1|val[i]);
}
}
int main(){
read(L),read(R);ll=L,rr=R;
st[0]=1,lg[1]=1;
for(int i=1;i<=20;i++){
st[i]=st[i-1]<<1;
lg[st[i]]=i+1;
}if(maxbit(L)==maxbit(R)){
tot=1,p2=tot,p1=++tot;
for(int i=maxbit(R);i>=1;i>>=1){
if((L&i)!=(R&i))break;
int tv=0;
if(L&i){tv=1;L-=i,R-=i;}
if(i==1||(!L&&!R)){
link(p1,p2,tv);
}else{
link(p1,++tot,tv);
//printf("LINK %d %d %d\n",p1,tot,tv);
p1=tot;
}
}int l=lg[maxbit(L)],r=lg[maxbit(R)];
//printf("TOT1 %d\n",tot);
if(l+1<=r-1){
//printf("%d to %d\n",l+1,r-1);
link(p1,p1+1,0);
link(p1+1,p1+2,1);
for(int i=2;i<r;i++){
if(i<r-1){
link(p1+i,p1+i+1,1);
link(p1+i,p1+i+1,0);
tot=p1+i+1;
}else{
link(p1+i,p2,1);
link(p1+i,p2,0);
}
}int tip=p1+1;
for(int i=1;i<=r-1-(l+1);i++){
link(tip,++tot,0);tip=tot;
link(tip,p1+i+2,1);
}
}int last=0,t1,t2;
for(int i=maxbit(R);i>=1;i>>=1){
if(i==maxbit(R)){
if(i>1){
link(p1,++tot,1);
t1=tot,t2=tot;
}else{
link(p1,p2,1);
link(p1,p2,0);
//printf("link %d and %d 01 %d\n",p1,p2,dig[p1]);
}continue;
}if(R&i){
if(!last){
last=i;
if(i>1){
link(t1,++tot,1);t1=tot;
link(t2,++tot,0);t2=tot;
}else{
link(t1,p2,1);
link(t1,p2,0);
}
}else{
if(i>1){
last=i;
link(t1,++tot,1);
link(t1,++tot,0);
link(t2,tot,0);
link(t2,tot,1);
t1=tot-1,t2=tot;
}else{
link(t1,p2,1);
link(t1,p2,0);
link(t2,p2,1);
link(t2,p2,0);
}
}
}else{
if(!last){
if(i>1){
link(t1,++tot,0);
t1=tot;t2=tot;
}else {
link(t1,p2,0);
}
}else{
if(i>1){
link(t1,++tot,0);t1=tot;
link(t2,++tot,1);
link(t2,tot,0);t2=tot;
}else{
link(t1,p2,0);
link(t2,p2,1);
link(t2,p2,0);
}
}
}
}
if(L){
for(int i=l;i<r;i++){
link(p1,++tot,0);p1=tot;
}last=0;
}
for(int i=maxbit(L);i>=1;i>>=1){
if(i==maxbit(L)){
if(i>1){
link(p1,++tot,1);
t1=tot,t2=tot;
}else{
link(p1,p2,1);
}continue;
}if(!(L&i)){
if(!last){
last=i;
if(i>1){
link(t1,++tot,0);t1=tot;
link(t2,++tot,1);t2=tot;
}else{
link(t1,p2,1);
}
}else{
if(i>1){
last=i;
link(t1,++tot,0);
link(t1,++tot,1);
link(t2,tot,1);
link(t2,tot,0);
t1=tot-1,t2=tot;
}else{
link(t1,p2,1);
link(t1,p2,0);
link(t2,p2,1);
link(t2,p2,0);
}
}
}else{
if(!last){
if(i>1){
link(t1,++tot,1);
t1=tot;t2=tot;
}else link(t1,p2,1);
}else{
if(i>1){
link(t1,++tot,1);t1=tot;
link(t2,++tot,0);
link(t2,tot,1);t2=tot;
}else{
link(t1,p2,1);
link(t2,p2,0);
link(t2,p2,1);
}
}
}
}
}else{
int l=lg[maxbit(L)],r=lg[maxbit(R)];
tot=1,p2=tot,p1=++tot;
if(l+1<=r-1){
//printf("ll %d rr %d\n",l+1,r-1);
link(p1,p1+1,1);tot=p1+1;
for(int i=1;i<r-1;i++){
if(l<=i){
link(p1+i,p2,1);
link(p1+i,p2,0);
}if(i<r-2){
link(p1+i,p1+i+1,1);
link(p1+i,p1+i+1,0);
tot=p1+i+1;
}
}
}int last=0,t1,t2;
for(int i=maxbit(R);i>=1;i>>=1){
if(i==maxbit(R)){
if(i>1){
link(p1,++tot,1);
t1=tot,t2=tot;
}else{
link(p1,p2,1);
}continue;
}if(R&i){
if(!last){
last=i;
if(i>1){
link(t1,++tot,1);t1=tot;
link(t2,++tot,0);t2=tot;
}else{
link(t1,p2,1);
link(t1,p2,0);
}
}else{
if(i>1){
last=i;
link(t1,++tot,1);
link(t1,++tot,0);
link(t2,tot,0);
link(t2,tot,1);
t1=tot-1,t2=tot;
}else{
link(t1,p2,1);
link(t1,p2,0);
link(t2,p2,1);
link(t2,p2,0);
}
}
}else{
if(!last){
if(i>1){
link(t1,++tot,0);
t1=tot;t2=tot;
}else {
link(t1,p2,0);
}
}else{
if(i>1){
link(t1,++tot,0);t1=tot;
link(t2,++tot,1);
link(t2,tot,0);t2=tot;
}else{
link(t1,p2,0);
link(t2,p2,1);
link(t2,p2,0);
}
}
}
}last=0;
for(int i=maxbit(L);i>=1;i>>=1){
if(i==maxbit(L)){
if(i>1){
link(p1,++tot,1);
t1=tot,t2=tot;
}else{
link(p1,p2,1);
}continue;
}if(!(L&i)){
if(!last){
last=i;
if(i>1){
link(t1,++tot,0);t1=tot;
link(t2,++tot,1);t2=tot;
}else{
link(t1,p2,1);
}
}else{
if(i>1){
last=i;
link(t1,++tot,0);
link(t1,++tot,1);
link(t2,tot,1);
link(t2,tot,0);
t1=tot-1,t2=tot;
}else{
link(t1,p2,1);
link(t1,p2,0);
link(t2,p2,1);
link(t2,p2,0);
}
}
}else{
if(!last){
if(i>1){
link(t1,++tot,1);
t1=tot;t2=tot;
}else link(t1,p2,1);
}else{
if(i>1){
link(t1,++tot,1);t1=tot;
link(t2,++tot,0);
link(t2,tot,1);t2=tot;
}else{
link(t1,p2,1);
link(t2,p2,0);
link(t2,p2,1);
}
}
}
}
}printf("%d\n",tot);
for(int i=1;i<=tot;i++){
printf("%d ",dig[i]);
for(int j=head[i];j;j=nxt[j]){
printf("%d %d ",to[j],val[j]);
}printf("\n");
}
dfs(2,0);
for(int i=ll;i<=rr;i++){
if(mp[i]<1){
printf("%d can not get\n",i);
}if(mp[i]>1){
printf("%d get twice\n",i);
}
}
return 0;
}
/*
123 545
*/
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9964kb
input:
5 7
output:
5 0 1 3 1 2 5 0 4 1 2 1 0 1 1 1 1 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 9900kb
input:
10 27
output:
14 0 2 10 1 3 1 2 5 0 4 1 1 6 0 2 7 0 7 1 2 9 0 8 1 2 9 1 9 0 2 1 0 1 1 2 1 0 1 1 2 12 1 11 0 1 13 1 2 14 1 14 0 2 1 0 1 1 2 1 0 1 1
result:
ok ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 9908kb
input:
5 13
output:
10 0 2 8 1 3 1 2 5 0 4 1 1 6 0 2 7 0 7 1 2 1 0 1 1 2 1 0 1 1 2 10 1 9 0 1 1 1 2 1 1 1 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 368ms
memory: 56768kb
input:
1 1000000
output:
57 0 3 1 1 21 1 3 1 4 4 0 4 1 1 0 1 1 4 5 0 5 1 1 0 1 1 4 6 0 6 1 1 0 1 1 4 7 0 7 1 1 0 1 1 4 8 0 8 1 1 0 1 1 4 9 0 9 1 1 0 1 1 4 10 0 10 1 1 0 1 1 4 11 0 11 1 1 0 1 1 4 12 0 12 1 1 0 1 1 4 13 0 13 1 1 0 1 1 4 14 0 14 1 1 0 1 1 4 15 0 15 1 1 0 1 1 4 16 0 16 1 1 0 1 1 4 17 0 17 1 1 0 1...
result:
ok ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 9956kb
input:
1 1
output:
2 0 1 1 1
result:
ok ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 9908kb
input:
7 9
output:
7 0 2 6 1 3 1 1 4 0 1 5 0 2 1 0 1 1 1 7 1 1 1 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 1ms
memory: 10032kb
input:
3 7
output:
6 0 2 6 1 3 1 2 5 0 4 1 2 1 0 1 1 2 1 0 1 1 1 1 1
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 9948kb
input:
1 5
output:
5 0 3 1 1 4 1 3 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: 9956kb
input:
1 4
output:
5 0 3 1 1 4 1 3 1 2 1 0 1 1 1 5 0 1 1 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 1ms
memory: 10008kb
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: 9924kb
input:
7 51
output:
17 0 3 16 1 7 1 3 1 2 4 0 4 1 2 5 0 5 1 4 6 0 6 1 1 0 1 1 2 1 0 1 1 2 9 0 8 1 1 10 0 2 11 0 11 1 1 12 0 2 13 0 13 1 2 15 0 14 1 2 15 1 15 0 2 1 0 1 1 2 1 0 1 1 1 17 1 1 1 1
result:
ok ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 9948kb
input:
51 79
output:
19 0 2 12 1 3 1 1 4 0 1 5 0 2 7 0 6 1 2 9 0 8 1 2 9 1 9 0 2 11 0 10 1 2 11 1 11 0 2 1 0 1 1 2 1 0 1 1 1 13 1 2 15 1 14 0 2 17 1 16 0 2 17 0 17 1 1 18 1 2 19 1 19 0 1 1 1 2 1 1 1 0
result:
ok ok
Test #13:
score: 0
Accepted
time: 1ms
memory: 9892kb
input:
92 99
output:
15 0 1 3 1 2 10 0 4 1 1 5 0 1 6 0 1 7 0 2 9 0 8 1 2 1 0 1 1 2 1 0 1 1 1 11 1 1 12 1 1 13 1 2 15 1 14 0 2 1 0 1 1 2 1 0 1 1
result:
ok ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 10036kb
input:
27 36
output:
15 0 2 10 1 3 1 1 4 0 1 5 0 2 7 0 6 1 1 8 0 2 9 0 9 1 1 1 0 2 1 0 1 1 1 11 1 2 13 1 12 0 1 14 1 2 15 1 15 0 1 1 1 2 1 1 1 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 1ms
memory: 9888kb
input:
55 84
output:
20 0 2 13 1 3 1 1 4 0 2 6 0 5 1 1 7 0 2 8 0 8 1 2 10 0 9 1 2 10 1 10 0 1 11 0 2 12 0 12 1 1 1 0 2 1 0 1 1 1 14 1 2 16 1 15 0 1 17 1 2 18 1 18 0 1 19 1 2 20 1 20 0 1 1 1 2 1 1 1 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 186ms
memory: 39592kb
input:
297208 929600
output:
74 0 2 40 1 3 1 2 5 0 4 1 2 7 0 6 1 2 7 1 7 0 1 8 0 2 9 0 9 1 1 10 0 2 11 0 11 1 1 12 0 2 13 0 13 1 2 15 0 14 1 2 15 1 15 0 1 16 0 2 17 0 17 1 2 19 0 18 1 2 19 1 19 0 2 21 0 20 1 2 21 1 21 0 2 23 0 22 1 2 23 1 23 0 2 25 0 24 1 2 25 1 25 0 1 26 0 2 27 0 27 1 2 29 0 28 1 2 29...
result:
ok ok
Test #17:
score: 0
Accepted
time: 169ms
memory: 35432kb
input:
45728 589156
output:
83 0 3 55 1 21 1 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 18 1 4 19 0 19 1 1 0 1 1 4 20 0 20 1 1 0 1 1 2 1 0 1 1 1 22 0 1 23 0 1 24 0 2 26 0 25 1 2 28...
result:
ok ok
Test #18:
score: 0
Accepted
time: 3ms
memory: 10396kb
input:
129152 138000
output:
57 0 2 32 1 3 1 1 4 0 1 5 0 1 6 0 1 7 0 2 9 0 8 1 2 11 0 10 1 2 11 1 11 0 1 12 0 2 13 0 13 1 2 15 0 14 1 2 15 1 15 0 2 17 0 16 1 2 17 1 17 0 1 18 0 2 19 0 19 1 1 20 0 2 21 0 21 1 1 22 0 2 23 0 23 1 2 25 0 24 1 2 25 1 25 0 1 26 0 2 27 0 27 1 1 28 0 2 29 0 29 1 1 30 0 2 31 ...
result:
ok ok
Test #19:
score: 0
Accepted
time: 116ms
memory: 29064kb
input:
245280 654141
output:
86 0 3 56 1 21 1 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 18 1 2 19 0 19 1 2 20 0 20 1 2 1 0 1 1 1 22 0 1 23 0 2 25 0 24 1 2 27 0 26 1 2 27 1 27 0 2 ...
result:
ok ok
Test #20:
score: 0
Accepted
time: 19ms
memory: 14244kb
input:
202985 296000
output:
67 0 2 36 1 3 1 1 4 0 1 5 0 2 7 0 6 1 1 8 0 2 9 0 9 1 1 10 0 2 11 0 11 1 1 12 0 2 13 0 13 1 1 14 0 2 15 0 15 1 2 17 0 16 1 2 17 1 17 0 1 18 0 2 19 0 19 1 1 20 0 2 21 0 21 1 1 22 0 2 23 0 23 1 2 25 0 24 1 2 25 1 25 0 1 26 0 2 27 0 27 1 1 28 0 2 29 0 29 1 1 30 0 2 31 0 31 1...
result:
ok ok
Test #21:
score: 0
Accepted
time: 149ms
memory: 33984kb
input:
438671 951305
output:
73 0 2 40 1 3 1 2 5 0 4 1 2 7 0 6 1 2 7 1 7 0 1 8 0 2 9 0 9 1 2 11 0 10 1 2 11 1 11 0 1 12 0 2 13 0 13 1 1 14 0 2 15 0 15 1 1 16 0 2 17 0 17 1 1 18 0 2 19 0 19 1 2 21 0 20 1 2 21 1 21 0 1 22 0 2 23 0 23 1 1 24 0 2 25 0 25 1 1 26 0 2 27 0 27 1 1 28 0 2 29 0 29 1 1 30 0 2 3...
result:
ok ok
Test #22:
score: 0
Accepted
time: 80ms
memory: 24840kb
input:
425249 739633
output:
72 0 2 39 1 3 1 1 4 0 2 6 0 5 1 2 8 0 7 1 2 8 1 8 0 1 9 0 2 10 0 10 1 2 12 0 11 1 2 12 1 12 0 1 13 0 2 14 0 14 1 1 15 0 2 16 0 16 1 2 18 0 17 1 2 18 1 18 0 1 19 0 2 20 0 20 1 1 21 0 2 22 0 22 1 2 24 0 23 1 2 24 1 24 0 1 25 0 2 26 0 26 1 1 27 0 2 28 0 28 1 2 30 0 29 1 2 30 ...
result:
ok ok
Test #23:
score: 0
Accepted
time: 137ms
memory: 29128kb
input:
551207 961718
output:
88 0 1 3 1 3 59 0 24 1 4 0 2 22 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 21 0 21 1 2 1 0 1 1 2 23 0 6 1 1 7 1 2 26 0 25 1 1 27 0 2 28 0 ...
result:
ok ok
Test #24:
score: 0
Accepted
time: 146ms
memory: 32708kb
input:
114691 598186
output:
84 0 3 56 1 21 1 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 18 1 2 19 0 19 1 4 20 0 20 1 1 0 1 1 2 1 0 1 1 1 22 0 1 23 0 2 25 0 24 1 1 26 0 2 27 0 27 1 ...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 10760kb
input:
234654 253129
output:
70 0 1 3 1 1 4 1 1 5 1 3 46 0 20 1 6 0 1 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 1 0 1 1 1 21 0 2 23 0 22 1 2 25 0 24 1 2 25 1 25 0 2 27 0 26 1 2 27 1 27 0 1 28 0 2 29 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 11ms
memory: 12664kb
input:
554090 608599
output:
78 0 1 3 1 1 4 0 1 5 0 3 52 0 22 1 6 0 1 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 21 0 21 1 2 1 0 1 1 1 23 0 2 25 0 24 1 1 26 0 2 27 0 27 1 1 28 0 2 29 0 29 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed