QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#749669#9519. Build a ComputerlegohuAC ✓3ms5952kbC++203.3kb2024-11-15 09:04:152024-11-15 09:04:17

Judging History

This is the latest submission verdict.

  • [2024-11-15 09:04:17]
  • Judged
  • Verdict: AC
  • Time: 3ms
  • Memory: 5952kb
  • [2024-11-15 09:04:15]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
    int v,dat;
    node(){}
    node(int V,int D){v=V;dat=D;}
    friend bool operator == (const node&a,const node&b){
        return a.v==b.v&&b.dat==a.dat;
    }
    friend bool operator <(const node&a,const node &b){
        if(a.v==b.v)return a.dat<b.dat;
        return a.v<b.v;
    }
};vector<node> g[N];
int tot=2,Ed=2;
int bitcount(int a){
    int siz=0;while(a){
        a>>=1;siz++;
    }return siz;
}
vector<int> lnk;int flg=0;
void diverses(int a,int b,int m,int p){
    //cout<<a<<' '<<b<<endl;
    if(a==2&&b==3){
        g[p].push_back(node(lnk[flg-m],1));return;
    }
    if((a==(1<<m-1))&&(b==(1<<m)-1)){
        //cout<<"yes";

        g[p].push_back(node(lnk[flg-m],1));
        return;
    }
    if(a==b){
        int x=!!(a&(1<<m-1));++tot;
        g[p].push_back(node(tot,x));
        p=tot;
        for(int i=m-2;i>0;i--){
            x=!!(a&(1<<i));++tot;
            g[p].push_back(node(tot,x));
            p=tot;
        }
        g[p].push_back(node(Ed,a&1));
        return;
    }
    int n=bitcount(a^b);
    for(int i=m;i>n;i--){
        ++tot;
        if(a&(1<<i-1))g[p].push_back(node(tot,1));
        else g[p].push_back(node(tot,0));
        p=tot;
    }

    int fa=p,fb=p;
    for(int i=n;i>0;i--){
        int x=!!(a&(1<<i-1)),y=!!(b&(1<<i-1));int nfa,nfb;
        if(i!=1){
        ++tot;g[fa].push_back(node(tot,x));nfa=tot;
        ++tot;g[fb].push_back(node(tot,y));nfb=tot;
        }else{
            g[fa].push_back(node(Ed,x));
            g[fb].push_back(node(Ed,y));
        }
        //if(flg-i>=lnk.size())printf("Danger!");
        if(fa!=p&&x==0)g[fa].push_back(node(lnk[flg-i],1));
        if(fb!=p&&y==1)g[fb].push_back(node(lnk[flg-i],0));
        fa=nfa;fb=nfb;
    }
}
int vis[N],nt;
vector<node> e[N];
void dfs(int p){
    if(vis[p])return;vis[p]=++nt;
    for(int i=0;i<g[p].size();i++){
        int v=g[p][i].v;
        //cout<<p<<" "<<v<<" "<<g[p][i].dat<<endl;
        dfs(v);
        e[vis[p]].push_back(node(vis[v],g[p][i].dat));
    }
}
int main(){
    int L,R;cin>>L>>R;
    int st=bitcount(L)-1,ed=bitcount(R);
    int mx=tot;
    int ii=bitcount(R);
    flg=ii;
    for(int j=ii;j>2;j--){
        tot++;
        lnk.push_back(tot);
        g[tot].push_back(node(tot+1,0));
        g[tot].push_back(node(tot+1,1));
    }
    if(ii>1){
        tot++;
        lnk.push_back(tot);
        g[tot].push_back(node(Ed,0));
        g[tot].push_back(node(Ed,1));
    }lnk.push_back(Ed);
    //for(int i=0;i<lnk.size();i++)cout<<lnk[i]<<',';cout<<endl;

    lnk.push_back(Ed);
    //cout<<"lnk_finish\n";
    for(int i=st;i<ed;i++){
        diverses(max(L,1<<i),min(R,(1<<i+1)-1),i+1,1);
        mx=max(mx,tot);
    }
    //cout<<"diversed\n";
    //cout<<tot<<endl;
    dfs(1);//return 0;
    cout<<nt<<endl;
    for(int i=1;i<=nt;i++){sort(e[i].begin(),e[i].end());e[i].erase(unique(e[i].begin(),e[i].end()),e[i].end());}
    for(int i=1;i<=nt;i++){
        printf("%d ",e[i].size());
        for(int j=0;j<e[i].size();j++)
        {
            int v=e[i][j].v;
            printf("%d %d ",v,e[i][j].dat);
        }
        printf("\n");
    }
    printf("\n");

    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 5892kb

input:

5 7

output:

5
1 2 1 
2 3 0 5 1 
1 4 1 
0 
2 4 0 4 1 


result:

ok ok

Test #2:

score: 0
Accepted
time: 3ms
memory: 5824kb

input:

10 27

output:

16
2 2 1 9 1 
2 3 0 6 1 
1 4 1 
2 5 0 5 1 
0 
2 7 1 8 0 
2 5 0 5 1 
2 5 0 5 1 
2 10 0 14 1 
2 11 0 13 1 
2 8 1 12 0 
2 5 0 5 1 
2 8 0 8 1 
1 15 0 
2 8 0 16 1 
2 5 0 5 1 


result:

ok ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 5824kb

input:

5 13

output:

11
2 2 1 6 1 
2 3 0 5 1 
1 4 1 
0 
2 4 0 4 1 
2 7 0 10 1 
2 8 0 9 1 
2 4 0 4 1 
2 4 0 4 1 
1 11 0 
2 4 0 4 1 


result:

ok ok

Test #4:

score: 0
Accepted
time: 0ms
memory: 5948kb

input:

1 1000000

output:

57
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: 3ms
memory: 5952kb

input:

1 1

output:

2
1 2 1 
0 


result:

ok ok

Test #6:

score: 0
Accepted
time: 3ms
memory: 5824kb

input:

7 9

output:

7
2 2 1 5 1 
1 3 1 
1 4 1 
0 
1 6 0 
1 7 0 
2 4 0 4 1 


result:

ok ok

Test #7:

score: 0
Accepted
time: 3ms
memory: 5908kb

input:

3 7

output:

5
2 2 1 4 1 
1 3 1 
0 
2 5 0 5 1 
2 3 0 3 1 


result:

ok ok

Test #8:

score: 0
Accepted
time: 0ms
memory: 5952kb

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: 5824kb

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: 5880kb

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: 5868kb

input:

7 51

output:

17
4 2 1 5 1 8 1 9 1 
1 3 1 
1 4 1 
0 
2 6 0 6 1 
2 7 0 7 1 
2 4 0 4 1 
2 5 0 5 1 
2 10 0 14 1 
2 5 1 11 0 
2 6 1 12 0 
2 7 1 13 0 
2 4 0 4 1 
1 15 0 
1 16 0 
2 7 0 17 1 
2 4 0 4 1 


result:

ok ok

Test #12:

score: 0
Accepted
time: 3ms
memory: 5824kb

input:

51 79

output:

21
2 2 1 13 1 
1 3 1 
2 4 0 10 1 
2 5 0 8 1 
1 6 1 
1 7 1 
0 
2 9 0 9 1 
2 7 0 7 1 
2 8 0 11 1 
2 9 0 12 1 
2 7 0 7 1 
1 14 0 
1 15 0 
2 16 0 19 1 
2 8 1 17 0 
2 9 1 18 0 
2 7 0 7 1 
2 8 0 20 1 
2 9 0 21 1 
2 7 0 7 1 


result:

ok ok

Test #13:

score: 0
Accepted
time: 2ms
memory: 5872kb

input:

92 99

output:

14
1 2 1 
2 3 0 10 1 
1 4 1 
1 5 1 
1 6 1 
2 7 0 9 1 
2 8 0 8 1 
0 
2 8 0 8 1 
1 11 0 
1 12 0 
1 13 0 
2 9 0 14 1 
2 8 0 8 1 


result:

ok ok

Test #14:

score: 0
Accepted
time: 3ms
memory: 5888kb

input:

27 36

output:

16
2 2 1 10 1 
1 3 1 
2 4 0 7 1 
1 5 1 
1 6 1 
0 
2 8 1 9 0 
2 6 0 6 1 
2 6 0 6 1 
1 11 0 
1 12 0 
2 13 0 15 1 
2 9 1 14 0 
2 6 0 6 1 
1 16 0 
1 6 0 


result:

ok ok

Test #15:

score: 0
Accepted
time: 3ms
memory: 5904kb

input:

55 84

output:

23
2 2 1 13 1 
1 3 1 
2 4 0 8 1 
1 5 1 
1 6 1 
1 7 1 
0 
2 9 1 12 0 
2 10 1 11 0 
2 7 0 7 1 
2 7 0 7 1 
2 11 0 11 1 
1 14 0 
2 15 0 20 1 
2 16 0 19 1 
2 12 1 17 0 
2 11 1 18 0 
2 7 0 7 1 
2 12 0 12 1 
1 21 0 
2 12 0 22 1 
1 23 0 
1 7 0 


result:

ok ok

Test #16:

score: 0
Accepted
time: 3ms
memory: 5900kb

input:

297208 929600

output:

91
2 2 1 54 1 
2 3 0 37 1 
2 4 0 35 1 
1 5 1 
2 6 0 34 1 
2 7 0 33 1 
2 8 0 31 1 
1 9 1 
2 10 0 30 1 
2 11 0 29 1 
2 12 0 23 1 
1 13 1 
1 14 1 
1 15 1 
1 16 1 
1 17 1 
2 18 0 22 1 
2 19 0 21 1 
2 20 0 20 1 
0 
2 20 0 20 1 
2 21 0 21 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 1 ...

result:

ok ok

Test #17:

score: 0
Accepted
time: 3ms
memory: 5952kb

input:

45728 589156

output:

83
5 2 1 45 1 48 1 49 1 50 1 
2 3 0 29 1 
1 4 1 
1 5 1 
2 6 0 28 1 
2 7 0 26 1 
1 8 1 
2 9 0 24 1 
1 10 1 
2 11 0 22 1 
1 12 1 
2 13 0 21 1 
2 14 0 20 1 
2 15 0 19 1 
2 16 0 18 1 
2 17 0 17 1 
0 
2 17 0 17 1 
2 18 0 18 1 
2 19 0 19 1 
2 20 0 20 1 
2 23 0 23 1 
2 21 0 21 1 
2 25 0 25 1 
2 22 0 22 1 
...

result:

ok ok

Test #18:

score: 0
Accepted
time: 3ms
memory: 5824kb

input:

129152 138000

output:

68
2 2 1 38 1 
1 3 1 
1 4 1 
1 5 1 
1 6 1 
1 7 1 
2 8 0 28 1 
2 9 0 27 1 
2 10 0 25 1 
1 11 1 
2 12 0 24 1 
2 13 0 23 1 
2 14 0 22 1 
2 15 0 21 1 
2 16 0 20 1 
2 17 0 19 1 
2 18 0 18 1 
0 
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 26 0 26 1 
2 24 0 24 1 
2 25 0 ...

result:

ok ok

Test #19:

score: 0
Accepted
time: 0ms
memory: 5904kb

input:

245280 654141

output:

86
3 2 1 47 1 52 1 
1 3 1 
1 4 1 
2 5 0 28 1 
1 6 1 
1 7 1 
1 8 1 
1 9 1 
1 10 1 
2 11 0 27 1 
2 12 0 26 1 
2 13 0 24 1 
1 14 1 
2 15 0 23 1 
2 16 0 22 1 
2 17 0 21 1 
2 18 0 20 1 
2 19 0 19 1 
0 
2 19 0 19 1 
2 20 0 20 1 
2 21 0 21 1 
2 22 0 22 1 
2 25 0 25 1 
2 23 0 23 1 
2 24 0 24 1 
2 26 0 26 1 ...

result:

ok ok

Test #20:

score: 0
Accepted
time: 0ms
memory: 5892kb

input:

202985 296000

output:

81
2 2 1 49 1 
1 3 1 
2 4 0 34 1 
2 5 0 33 1 
2 6 0 30 1 
1 7 1 
1 8 1 
2 9 0 29 1 
2 10 0 28 1 
2 11 0 24 1 
1 12 1 
1 13 1 
1 14 1 
2 15 0 22 1 
1 16 1 
2 17 0 21 1 
2 18 0 20 1 
1 19 1 
0 
2 19 0 19 1 
2 20 0 20 1 
2 23 0 23 1 
2 21 0 21 1 
2 25 0 25 1 
2 26 0 26 1 
2 27 0 27 1 
2 22 0 22 1 
2 24...

result:

ok ok

Test #21:

score: 0
Accepted
time: 3ms
memory: 5896kb

input:

438671 951305

output:

90
2 2 1 52 1 
1 3 1 
2 4 0 35 1 
1 5 1 
2 6 0 32 1 
1 7 1 
1 8 1 
2 9 0 31 1 
2 10 0 30 1 
2 11 0 27 1 
1 12 1 
1 13 1 
2 14 0 26 1 
2 15 0 25 1 
2 16 0 21 1 
1 17 1 
1 18 1 
1 19 1 
1 20 1 
0 
2 22 0 22 1 
2 23 0 23 1 
2 24 0 24 1 
2 20 0 20 1 
2 21 0 21 1 
2 25 0 25 1 
2 28 0 28 1 
2 29 0 29 1 
2...

result:

ok ok

Test #22:

score: 0
Accepted
time: 3ms
memory: 5900kb

input:

425249 739633

output:

88
2 2 1 52 1 
1 3 1 
2 4 0 36 1 
2 5 0 30 1 
1 6 1 
1 7 1 
1 8 1 
1 9 1 
1 10 1 
2 11 0 28 1 
1 12 1 
2 13 0 27 1 
2 14 0 25 1 
1 15 1 
2 16 0 24 1 
2 17 0 23 1 
2 18 0 22 1 
2 19 0 21 1 
1 20 1 
0 
2 20 0 20 1 
2 21 0 21 1 
2 22 0 22 1 
2 23 0 23 1 
2 26 0 26 1 
2 24 0 24 1 
2 25 0 25 1 
2 29 0 29...

result:

ok ok

Test #23:

score: 0
Accepted
time: 0ms
memory: 5896kb

input:

551207 961718

output:

56
1 2 1 
2 3 0 39 1 
2 4 0 38 1 
2 5 0 37 1 
2 6 0 34 1 
1 7 1 
1 8 1 
2 9 0 32 1 
1 10 1 
2 11 0 31 1 
2 12 0 29 1 
1 13 1 
2 14 0 28 1 
2 15 0 26 1 
1 16 1 
2 17 0 25 1 
2 18 0 22 1 
1 19 1 
1 20 1 
1 21 1 
0 
2 23 0 23 1 
2 24 0 24 1 
2 21 0 21 1 
2 22 0 22 1 
2 27 0 27 1 
2 25 0 25 1 
2 26 0 26...

result:

ok ok

Test #24:

score: 0
Accepted
time: 2ms
memory: 5868kb

input:

114691 598186

output:

84
4 2 1 44 1 49 1 50 1 
1 3 1 
1 4 1 
2 5 0 31 1 
2 6 0 30 1 
2 7 0 29 1 
2 8 0 28 1 
2 9 0 27 1 
2 10 0 26 1 
2 11 0 25 1 
2 12 0 24 1 
2 13 0 23 1 
2 14 0 22 1 
2 15 0 21 1 
2 16 0 19 1 
1 17 1 
1 18 1 
0 
2 20 0 20 1 
2 18 0 18 1 
2 19 0 19 1 
2 21 0 21 1 
2 22 0 22 1 
2 23 0 23 1 
2 24 0 24 1 
...

result:

ok ok

Test #25:

score: 0
Accepted
time: 3ms
memory: 5904kb

input:

234654 253129

output:

46
1 2 1 
1 3 1 
1 4 1 
2 5 0 33 1 
2 6 0 31 1 
1 7 1 
2 8 0 29 1 
1 9 1 
2 10 0 28 1 
2 11 0 26 1 
1 12 1 
2 13 0 25 1 
2 14 0 20 1 
1 15 1 
1 16 1 
1 17 1 
1 18 1 
2 19 0 19 1 
0 
2 21 0 21 1 
2 22 0 22 1 
2 23 0 23 1 
2 24 0 24 1 
2 19 0 19 1 
2 20 0 20 1 
2 27 0 27 1 
2 25 0 25 1 
2 26 0 26 1 
2...

result:

ok ok

Test #26:

score: 0
Accepted
time: 3ms
memory: 5912kb

input:

554090 608599

output:

52
1 2 1 
1 3 0 
1 4 0 
2 5 0 37 1 
2 6 0 33 1 
1 7 1 
1 8 1 
1 9 1 
2 10 0 31 1 
1 11 1 
2 12 0 30 1 
2 13 0 29 1 
2 14 0 26 1 
1 15 1 
1 16 1 
2 17 0 24 1 
1 18 1 
2 19 0 22 1 
1 20 1 
2 21 0 21 1 
0 
2 23 0 23 1 
2 21 0 21 1 
2 25 0 25 1 
2 22 0 22 1 
2 27 0 27 1 
2 28 0 28 1 
2 24 0 24 1 
2 26 0...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed