QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694656#9530. A Game On TreeYoshinow2001#WA 0ms3616kbC++202.3kb2024-10-31 18:25:042024-10-31 18:25:05

Judging History

This is the latest submission verdict.

  • [2024-10-31 18:25:05]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3616kb
  • [2024-10-31 18:25:04]
  • Submitted

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
// #define int long long 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int lowbit(int x){
    return x & (-x);
}
int higbit(int x){
    for(int i = 20;i >= 0;i--){
        if(x >> i & 1) return (1 << i);
    }
}
// nxt , w
vector<pair<int,int>> adj[2000];
int f(int x){
    return 21 - x; 
}

int Lg2(int x) {
    int r = 0;
    while (x) {
        x /= 2;
        r++;
    }
    return r - 1;
}

void solve() {
    int L , R;
    cin >> L >> R;
    for(int i = 1;i <= 20;i++){
        adj[i].push_back({ i + 1 , 0});
        adj[i].push_back({ i + 1 , 1});
    }
    int cnt = 21;
    for(int x = Lg2(lowbit(L));( 1 << x ) <= L;x++){
        cnt++;
        if(x >  Lg2(lowbit(L)))
        adj[cnt].push_back({ cnt - 1 , L >> x & 1});
    }
    int st = cnt;
    int LL = L;
    while(L + lowbit(L) <= R){
        int nxt = lowbit(L);
        int lg = Lg2(nxt);
        if(lowbit(L) > higbit(LL)){
            //cout <<"##"<<endl;
           adj[st].push_back({f(lg) , 1});
        }
        else {
            adj[21 + lg -  Lg2(lowbit(L)) + 1].push_back({21 - lg, 1});
        }
        L += lowbit(L);
    }
    int x = Lg2(R);
    int P = cnt;
    for(int i = 0;i < x;i++){
        ++cnt;
        if(i > 0) adj[cnt].push_back({cnt - 1, R >> i & 1});
        else adj[cnt].push_back({f(0), R >> i & 1});
    }
    adj[st].push_back({cnt , 1});
    while(L < R){
        int dx = higbit(L ^ R);
        int g = Lg2(dx);
        adj[P + g + 1].push_back({f(g) , 0});
        L += dx;
    }
    vector<int> deg(200);
    for(int i = 22; i <= cnt;i++){
        for(auto [x , y] : adj[i]) deg[x] = 1;
    }
    int D = 0;
    for(int i = 1; i <= 21;i++){
        if(deg[i] == 1){
            D = i - 1;
            break;
        }
    }
    cout << cnt - D << endl;
    for(int i = 1 ; i <= cnt - D;i++){
        int p = i + D;
        cout << adj[p].size() << " ";
        for(auto [x , y] : adj[p]){
            x -= D;
            cout << x <<' '<< y <<' ';
        }
        cout << endl;
    }

}

int32_t main(){
    fastio;
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}

详细

Test #1:

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

input:

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

output:

3
0 
1 3 1 
2 1 1 1 0 

result:

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