QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#680300#9519. Build a Computerucup-team5351#AC ✓1ms4104kbC++143.7kb2024-10-26 20:33:132024-10-26 20:33:17

Judging History

This is the latest submission verdict.

  • [2024-10-26 20:33:17]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 4104kb
  • [2024-10-26 20:33:13]
  • Submitted

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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