QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#698156#9519. Build a ComputerTecyAC ✓1ms3908kbC++143.7kb2024-11-01 17:47:502024-11-01 17:47:51

Judging History

This is the latest submission verdict.

  • [2024-11-01 17:47:51]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3908kb
  • [2024-11-01 17:47:50]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(a,b,c) for(ll a=b;a<=(c);a++)
#define drep(a,b,c) for(ll a=b;a>=(c);a--)
#define io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define dpq priority_queue<ll, vector<ll>, less<ll> > 
#define pq priority_queue<ll, vector<ll>, greater<ll> > //push pop
#define spq priority_queue<string>
#define pairqueue priority_queue<pair<ll,ll>>
#define mls multiset  //insert erase迭代器 extract具体元素
#define ull unsigned long long
#define PI 3.14159265358979323846
const ll inf =0x3f3f3f3f3f3f3f;
#define mod 1000000007
#define N 2000100
map<ll, map<ll,ll>>mp0; map<ll, map<ll, ll>>mp1;
map<ll ,map<ll,ll>>mp;//你清空map了吗?
ll a[N],b[N];
ll mi[N];
void solve()
{
    ll l,r;
    cin>>l>>r;
    mi[0]=1;
    rep(i,1,21)
    {
        mi[i]=mi[i-1]*2;
    }
    ll maxn=0;
    ll lenth=r-l+1;
    ll left=l,right=r;
    while(lenth!=0)
    {
        drep(i,21,0)
        {
            if(lenth>=mi[i]&&(right+1)%mi[i]==0)
            {
                maxn=max(maxn,i);
                lenth-=mi[i];
                right=right-mi[i];
                break;
            }
        }
    }
    maxn++;
    ll tot=maxn+1;
    //cerr<<tot<<"\n";
    rep(i,2,maxn)
    {
        mp0[i][i-1]=1;
        mp1[i][i-1]=1;
    }
    lenth=r-l+1;
    left=l,right=r;
    while(lenth!=0)
    {
        drep(i,21,0)
        {
            if(lenth>=mi[i]&&(right+1)%mi[i]==0)
            {
                //cerr<<mi[i]<<"\n";
                ll temp=right/mi[i];
                //cerr<<temp<<"\n";
                stack<ll>q;
                while(temp)
                {
                    q.push(temp%2);
                    temp/=2;
                }
                if(!q.empty())
                {
                    ll last=0;
                    while(q.size()>1)
                    {
                        ll num=q.top();
                        q.pop();
                        if(mp[last].count(num))
                        {
                            last=mp[last][num];
                        }
                        else
                        {
                            if(num==1)
                            {
                                mp1[last][tot]=1;
                            }
                            else mp0[last][tot]=1;
                            //cerr<<last<<" "<<tot<<"\n";
                            mp[last][num]=tot;
                            last=tot;
                            tot++;
                        }
                    }
                    ll num=q.top();
                    q.pop();
                    if(num==1)
                    {
                        mp1[last][i+1]=1;
                    }
                    else mp0[last][i+1]=1;
                    //tot++;
                }
                else
                {
                    mp1[0][i+1]=1;
                    mp0[0][i+1]=1;
                }
                lenth-=mi[i];
                right=right-mi[i];
                break;
            }
        }
        //cerr<<lenth<<" "<<tot<<"\n";
    }
    cout<<tot<<"\n";
    rep(i,0,tot-1)
    {
        ll ans=0;
        for(auto b:mp0[i])
        {
            ans++;
        }
        for(auto b:mp1[i])
        {
            ans++;
        }
        cout<<ans<<" ";
        for(auto b:mp0[i])
        {
            cout<<b.first+1<<" "<<0<<" ";
        }
        for(auto b:mp1[i])
        {
            cout<<b.first+1<<" "<<1<<" ";
        }
        cout<<"\n";
    }
}
int main()
{
    io;
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

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

詳細信息

Test #1:

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

input:

5 7

output:

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

result:

ok ok

Test #2:

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

input:

10 27

output:

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

result:

ok ok

Test #3:

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

input:

5 13

output:

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

result:

ok ok

Test #4:

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

input:

1 1000000

output:

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

input:

1 1

output:

2
1 2 1 
0 

result:

ok ok

Test #6:

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

input:

7 9

output:

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

result:

ok ok

Test #7:

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

input:

3 7

output:

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

result:

ok ok

Test #8:

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

input:

1 5

output:

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

result:

ok ok

Test #9:

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

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

input:

8 9

output:

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

result:

ok ok

Test #11:

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

input:

7 51

output:

9
3 5 1 6 1 7 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 8 1 
2 9 0 2 1 
1 4 0 

result:

ok ok

Test #12:

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

input:

51 79

output:

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

result:

ok ok

Test #13:

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

input:

92 99

output:

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

result:

ok ok

Test #14:

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

input:

27 36

output:

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

result:

ok ok

Test #15:

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

input:

55 84

output:

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

result:

ok ok

Test #16:

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

input:

297208 929600

output:

53
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 18 1 
2 19 0 19 1 
4 20 0 40 0 19 1 22 1 
2 19 0 23 1 
1 24 0 
1 25 0 
1 26 0 
2 15 0 2...

result:

ok ok

Test #17:

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

input:

45728 589156

output:

47
4 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 18 1 
2 19 0 19 1 
2 22 0 16 1 
2 23 0 40 1 
1 24 0 
2 17 0 25 1 
2 16 0...

result:

ok ok

Test #18:

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

input:

129152 138000

output:

39
1 15 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 16 0 32 1 
1 17 0 
1 18 0 
1 19 0 
2 14 0 20 1 
2 13 0 21 1 
1 22 0 
2 11 0 23 1 
2 10 0 24 1 
1 25 0 
1 26 0 
1 27 0 
2 6 0 28 1 
1 29 0 
1 30 ...

result:

ok ok

Test #19:

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

input:

245280 654141

output:

49
2 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 18 1 
2 19 0 19 1 
2 22 0 39 1 
1 23 0 
2 18 0 24 1 
2 17 0 25 1 
2 16 0 26 1 
2 1...

result:

ok ok

Test #20:

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

input:

202985 296000

output:

51
1 18 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 19 0 36 1 
1 20 0 
2 17 0 21 1 
1 22 0 
1 23 0 
1 24 0 
1 25 0 
2 12 0 26 1 
1 27 0 
1 28 0 
1 29 0 
2 8 ...

result:

ok ok

Test #21:

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

input:

438671 951305

output:

54
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 18 1 
2 19 0 19 1 
2 20 0 22 1 
4 19 0 39 0 18 1 23 1 
1 24 0 
2 17 0 25 1 
1 26 0 
1 2...

result:

ok ok

Test #22:

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

input:

425249 739633

output:

54
1 20 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 18 1 
2 21 0 38 1 
2 19 0 22 1 
2 18 0 23 1 
1 24 0 
2 16 0 25 1 
1 26 0 
1 27 0 
2 13 ...

result:

ok ok

Test #23:

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

input:

551207 961718

output:

56
1 20 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 18 1 
2 39 0 21 1 
2 19 0 22 1 
1 23 0 
2 17 0 24 1 
1 25 0 
2 15 0 26 1 
1 27 0 
2 13 ...

result:

ok ok

Test #24:

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

input:

114691 598186

output:

54
3 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 18 1 
2 19 0 19 1 
2 22 0 40 1 
1 23 0 
2 18 0 24 1 
1 25 0 
1 26 0 
2 15 0 2...

result:

ok ok

Test #25:

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

input:

234654 253129

output:

44
1 16 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 
1 17 1 
1 18 1 
2 32 0 19 1 
1 20 0 
2 14 0 21 1 
2 13 0 22 1 
2 12 0 23 1 
1 24 0 
1 25 0 
2 9 0 26 1 
2 8 0 27 1 
1 28 0 
1 29 0 
2...

result:

ok ok

Test #26:

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

input:

554090 608599

output:

48
1 18 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 
1 19 0 
1 20 0 
2 34 0 21 1 
1 22 0 
2 16 0 23 1 
1 24 0 
1 25 0 
2 13 0 26 1 
1 27 0 
1 28 0 
2 10 0 29 1 ...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed