QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#522797 | #9176. Non-Interactive Nim | hhu_yjh | WA | 0ms | 3584kb | C++17 | 1.6kb | 2024-08-17 14:37:43 | 2024-08-17 14:37:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
typedef long long ll;
typedef pair<ll, ll> PII;
ll n, k;
ll a[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
vector<set<int>> cnt(63); // 63位,0到62
for (int i = 1; i <= n; i++) {
for (int j = 62; j >= 0; j--) {
if (a[i] >> j & 1) {
cnt[j].insert(i);
break; // 只插入最高有效位
}
}
}
vector<pair<ll, ll>> ans;
auto work = [&](ll x, ll y) {
ll temp = 0;
for (int k = 62; k >= 0; k--) {
if ((a[x] >> k & 1) && (a[y] >> k & 1)) {
cnt[k].erase(x);
cnt[k].erase(y);
a[x] -= 1ll << k;
a[y] -= 1ll << k;
temp += 1ll << k;
if (a[x] > 0) cnt[k].insert(x);
if (a[y] > 0) cnt[k].insert(y);
}
}
ans.push_back({x, temp});
};
for (int i = 62; i >= 0; i--) {
if (cnt[i].size() == 0) continue;
if (cnt[i].size() != 2) {
cout << -1 << endl;
return;
}
ll x = *cnt[i].begin();
cnt[i].erase(x);
ll y = *cnt[i].begin();
cnt[i].clear();
work(x, y);
}
cout << ans.size() << endl;
for (auto j : ans) {
cout << j.first << ' ' << j.second << endl;
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3584kb
input:
2 4 4 2 7 1 4 1 1 1 1
output:
-1 -1
result:
wrong answer judge has answer but participant doesn't (test case 1)