QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#694656 | #9530. A Game On Tree | Yoshinow2001# | WA | 0ms | 3616kb | C++20 | 2.3kb | 2024-10-31 18:25:04 | 2024-10-31 18:25:05 |
Judging History
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'