QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#696355 | #9530. A Game On Tree | dreamwave# | WA | 0ms | 3620kb | C++14 | 2.6kb | 2024-10-31 22:11:56 | 2024-10-31 22:11:56 |
Judging History
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'