QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721894#9519. Build a Computerxiaoxiao__AC ✓4ms3836kbC++203.2kb2024-11-07 17:07:192024-11-07 17:07:19

Judging History

This is the latest submission verdict.

  • [2024-11-07 17:07:19]
  • Judged
  • Verdict: AC
  • Time: 4ms
  • Memory: 3836kb
  • [2024-11-07 17:07:19]
  • Submitted

answer

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<bitset>
#include<cstring>
#include<queue>
#define fi first
#define se second
using namespace std;
using ll=long long;
typedef pair<int,int>pii;
const int N=110;
int du[N];
vector<pii>e[N];//add
int er[23],q[23];
int dian[N];
int st=1,ed=2,idx=2;
int add(int suf){//solve the edges like 1_{01}_{01}...  
    if(suf==0)return ed;
    if(dian[suf])return dian[suf];
    int x=add(suf-1);
    idx++;
    e[idx].push_back({x,0});
    e[idx].push_back({x,1});
    return dian[suf]=idx;
}
int son[N][2];// 01 dictionary tree
int get(int x,string go){
    for(int i=0;i<go.length();i++){
        char ch=go[i];
        if(!son[x][ch-'0']){
            son[x][ch-'0']=++idx;
            e[x].push_back({son[x][ch-'0'],ch-'0'});
        }
        x=son[x][ch-'0'];
    }
    return x;
}
void dfs(string s,int X,int wei,int l,int r){
    // cout<<s<<' '<<X<<' '<<wei<<' '<<l<<' '<<r<<'\n';
    if(X>r)return;
    // cout<<s<<' '<<X<<'\n';
    if(wei==1){
        //cout<<X<<' ';
        if(X>=l&&X<=r){
            int x=get(st,s);
            e[x].push_back({ed,0});
        }
        if(X+1>=l&&X+1<=r){
            int x=get(st,s);
            e[x].push_back({ed,1});
        }
        return;
    }
    // if(X+q[wei-1]<l)return;
    if(X>=l&&X<=r&&X+q[wei-1]>=l&&X+q[wei-1]<=r){
        // cout<<s<<' '<<X<<' '<<wei<<' '<<l<<' '<<r<<'\n';
        // string tmp=s;
        // tmp.pop_back();
        int x=get(st,s);
        e[x].push_back({add(wei-1),0});
        e[x].push_back({add(wei-1),1});
        return;
    }
    dfs(s+"0",X,wei-1,l,r);
    dfs(s+"1",X+(1<<(wei-1)),wei-1,l,r);
}
int get_wei(int x){
    for(int i=21;i>=0;i--){
        if(x>>i&1)return i;
    }
}
void solve(int l,int r){
    int nw=1,cnt=0;
    int res=1;
    
    while(res+(nw<<1)<=r){
        nw<<=1;
        res+=nw;
    }
    nw=1;
    while(nw<l)nw<<=1,cnt++;
    //cout<<nw<<'\n';
    int l2=l,r2=min(nw-1,r);
    int wei=get_wei(l2);
    // cout<<wei<<'\n';
    // cout<<l2<<' '<<r2<<'\n';
    if(l2<=r2)dfs("1",1<<wei,wei,l2,r2);
    // cout<<nw<<' '<<res<<'\n';
    while(nw<=res){
        e[st].push_back({add(cnt++),1});
        nw<<=1;
    }
    // cout<<nw<<' ';
    //cout<<nw<<'\n';
    l2=nw;r2=r;
    wei=get_wei(l2);
    // cout<<l2<<' '<<r2<<'\n';
    if(l2<=r2)dfs("1",1<<wei,wei,l2,r2);
}
void silverwolf(){
    int l,r;
    cin>>l>>r;
    solve(l,r);
    cout<<idx<<'\n';
    for(int i=1;i<=idx;i++){
    //    cout<<"i="<<i<<":";
        cout<<e[i].size()<<' ';
        for(auto [x,w]:e[i])cout<<x<<' '<<w<<' ';cout<<'\n';
        
        // cout<<'\n';
        // for(auto [x,w]:e[i]){
        //     cout<<i<<' '<<x<<' '<<w<<'\n';
        // }
        // cout<<'\n';
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    er[0]=1;
    q[0]=1;
    for(int i=1;i<=20;i++)er[i]=er[i-1]*2;
    for(int i=1;i<=20;i++)q[i]=q[i-1]+er[i];
    // for(int i=0;i<=3;i++)cout<<q[i]<<' ';cout<<'\n';
    // cout<<q[4]<<'\n';
    //int T;cin>>T;while(T--)
    silverwolf();
    return 0;
}

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

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3780kb

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

input:

10 27

output:

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

result:

ok ok

Test #3:

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

input:

5 13

output:

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

result:

ok ok

Test #4:

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

input:

1 1000000

output:

45
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: 3832kb

input:

1 1

output:

2
1 2 1 
0 

result:

ok ok

Test #6:

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

input:

7 9

output:

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

result:

ok ok

Test #7:

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

input:

3 7

output:

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

result:

ok ok

Test #8:

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

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

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

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

input:

7 51

output:

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

result:

ok ok

Test #12:

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

input:

51 79

output:

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

result:

ok ok

Test #13:

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

input:

92 99

output:

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

result:

ok ok

Test #14:

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

input:

27 36

output:

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

result:

ok ok

Test #15:

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

input:

55 84

output:

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

result:

ok ok

Test #16:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

297208 929600

output:

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

result:

ok ok

Test #17:

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

input:

45728 589156

output:

63
4 3 1 34 1 35 1 36 1 
0 
2 4 0 28 1 
2 5 1 37 0 
1 6 1 
2 7 0 26 1 
2 8 0 23 1 
1 9 1 
2 10 0 20 1 
1 11 1 
2 12 0 18 1 
1 13 1 
2 17 0 17 1 
2 2 0 2 1 
2 14 0 14 1 
2 15 0 15 1 
2 16 0 16 1 
2 19 0 19 1 
2 17 0 17 1 
2 22 0 22 1 
2 19 0 19 1 
2 21 0 21 1 
2 25 0 25 1 
2 22 0 22 1 
2 24 0 24 1 
2...

result:

ok ok

Test #18:

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

input:

129152 138000

output:

47
1 3 1 
0 
2 4 1 25 0 
1 5 1 
1 6 1 
1 7 1 
1 8 1 
2 9 0 23 1 
2 10 0 21 1 
2 11 0 19 1 
1 12 1 
2 18 0 18 1 
2 2 0 2 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 0 20 1 
2 18 0 18 1 
2 22 0 22 1 
2 20 0 20 1 
2 24 0 24 1 
2 22 0 22 1 
1 26 0 
1 27 0 
1 28 0 
2 29 0 32 ...

result:

ok ok

Test #19:

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

input:

245280 654141

output:

67
2 3 1 37 1 
0 
2 4 1 38 0 
1 5 1 
2 6 0 26 1 
1 7 1 
1 8 1 
1 9 1 
1 10 1 
1 11 1 
2 12 0 24 1 
2 13 0 22 1 
2 14 0 20 1 
1 15 1 
2 19 0 19 1 
2 2 0 2 1 
2 16 0 16 1 
2 17 0 17 1 
2 18 0 18 1 
2 21 0 21 1 
2 19 0 19 1 
2 23 0 23 1 
2 21 0 21 1 
2 25 0 25 1 
2 23 0 23 1 
2 32 0 32 1 
2 25 0 25 1 
...

result:

ok ok

Test #20:

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

input:

202985 296000

output:

62
1 3 1 
0 
2 4 1 43 0 
2 5 0 41 1 
2 6 0 39 1 
2 7 0 35 1 
1 8 1 
1 9 1 
2 10 0 33 1 
2 11 0 31 1 
2 12 0 26 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 22 0 22 1 
2 2 0 2 1 
2 25 0 25 1 
2 22 0 22 1 
2 24 0 24 1 
2 30 0 30 1 
2 25 0 25 1 
2 27 0 2...

result:

ok ok

Test #21:

score: 0
Accepted
time: 4ms
memory: 3604kb

input:

438671 951305

output:

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

result:

ok ok

Test #22:

score: 0
Accepted
time: 4ms
memory: 3552kb

input:

425249 739633

output:

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

result:

ok ok

Test #23:

score: 0
Accepted
time: 1ms
memory: 3544kb

input:

551207 961718

output:

75
1 3 1 
0 
2 4 0 48 1 
2 5 0 46 1 
2 6 0 44 1 
2 7 0 40 1 
1 8 1 
1 9 1 
2 10 0 37 1 
1 11 1 
2 12 0 35 1 
2 13 0 32 1 
1 14 1 
2 15 0 30 1 
2 16 0 27 1 
1 17 1 
2 18 0 25 1 
2 19 0 22 1 
1 20 1 
1 21 1 
1 2 1 
2 24 0 24 1 
2 2 0 2 1 
2 23 0 23 1 
2 26 0 26 1 
2 24 0 24 1 
2 29 0 29 1 
2 26 0 26 1...

result:

ok ok

Test #24:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

114691 598186

output:

72
3 3 1 47 1 48 1 
0 
2 4 1 49 0 
1 5 1 
2 6 0 41 1 
2 7 0 39 1 
2 8 0 37 1 
2 9 0 35 1 
2 10 0 33 1 
2 11 0 31 1 
2 12 0 29 1 
2 13 0 27 1 
2 14 0 25 1 
2 15 0 23 1 
2 16 0 21 1 
2 17 0 19 1 
1 18 1 
1 2 1 
2 20 0 20 1 
2 2 0 2 1 
2 22 0 22 1 
2 20 0 20 1 
2 24 0 24 1 
2 22 0 22 1 
2 26 0 26 1 
2 ...

result:

ok ok

Test #25:

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

input:

234654 253129

output:

57
1 3 1 
0 
1 4 1 
1 5 1 
2 6 0 38 1 
2 7 0 35 1 
1 8 1 
2 9 0 32 1 
1 10 1 
2 11 0 30 1 
2 12 0 27 1 
1 13 1 
2 14 0 25 1 
2 15 0 20 1 
1 16 1 
1 17 1 
1 18 1 
1 19 1 
2 2 0 2 1 
2 24 0 24 1 
2 2 0 2 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 29 0 29 1 
2 26 0 26 1 
2 28...

result:

ok ok

Test #26:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

554090 608599

output:

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

result:

ok ok

Extra Test:

score: 0
Extra Test Passed