QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#696355#9530. A Game On Treedreamwave#WA 0ms3620kbC++142.6kb2024-10-31 22:11:562024-10-31 22:11:56

Judging History

This is the latest submission verdict.

  • [2024-10-31 22:11:56]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3620kb
  • [2024-10-31 22:11:56]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define N 21

inline vector<int> to2(int x){
    vector<int> res;
    for(int i=0;i<N&&x;++i){
        res.emplace_back(x&1);
        x>>=1;
    }
    return res;
}
vector<pair<int,int>> mp[110];
int tot=1;
inline void add(int u,int v,int w){
    mp[u].emplace_back(v,w);
}
inline void print(){
    cout<<tot<<endl;
    for(int i=1;i<=tot;++i){
//        cout<<i<<"-> ";
        cout<<mp[i].size()<<" ";
        for(auto [v,w]:mp[i]){
            cout<<v<<" "<<w<<" ";
        }
        cout<<endl;
    }
}
int id[110],idL[110],idR[110];
int L,R;


void solve() {
    cin>>L>>R;
    if(L==R){ 
        auto tmp=to2(L);
        for(int i=0;i<tmp.size();++i){
            tot++;
            add(i+2,i+1,tmp[i]);
        }
        print();
        return ;
    }
    auto L2=to2(L),R2=to2(R);
    int Lc=L2.size(),Rc=R2.size();
    
    L2.resize(N,0),R2.resize(N,0);
    
    int S=tot,T=++tot;
    idL[0]=T;
    if(Lc==1){
        idL[1]=S;
        add(S,T,1);
    }else for(int i=0;i<Lc;++i){
        if(i==0){
            idL[i+1]=++tot;
            add(tot,T,L2[i]);
        }
        else if(i==Lc-1){
            idL[i+1]=S;
            add(S,tot,L2[i]);
        }else{
            idL[i+1]=++tot;
            add(tot,tot-1,L2[i]);
        }
    }
    idR[0]=T;
    if(Rc==1){
        idR[1]=S;
        add(S,T,1);
    }else for(int i=0;i<Rc;++i){
        if(i==0){
            idR[i+1]=++tot;
            add(tot,T,R2[i]);
        }
        else if(i==Rc-1){
            idR[i+1]=S;
            add(S,tot,R2[i]);
        }else{
            idR[i+1]=++tot;
            add(tot,tot-1,R2[i]);
        }
    }

    int firstDif=0;
    for(int i=N-1;~i;--i) if(L2[i]!=R2[i]){
        firstDif=i;
        break;
    }
    // cout<<"firstDif: "<<firstDif<<endl;
    int cnt=0;
    for(int i=firstDif-1;~i;--i) if(L2[i]==0) cnt=max(cnt,i);
    for(int i=firstDif-1;~i;--i) if(R2[i]==1) cnt=max(cnt,i);
    // cout<<"cnt: "<<cnt <<endl;

    id[0]=T;
    for(int i=1;i<=cnt;++i){
        id[i]=++tot;
        add(id[i],id[i-1],0);
        add(id[i],id[i-1],1);
    }
    
    for(int i=Lc+1;i<=N;++i) idL[i]=S;
    for(int i=cnt;~i;--i) if(L2[i]==0){
        add(idL[i+1],id[i],1);
    }
    for(int i=cnt;~i;--i) if(R2[i]==1){
        add(idR[i+1],id[i],0);
    }

    print();
}

signed main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);
    int T = 1;
    // std::cin >> T;
    while(T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3620kb

input:

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

output:

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

result:

wrong answer 1st lines differ - expected: '443664158', found: '4'