QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#523487 | #9176. Non-Interactive Nim | ucup-team3282 | RE | 0ms | 3552kb | C++14 | 958b | 2024-08-18 12:22:57 | 2024-08-18 12:22:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int T;
int n;
ll a[maxn];
set<ll> b[60];
queue<int> q;
vector<pair<int,int> >ans;
int main(){
ios::sync_with_stdio(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
for(int k=0;k<60;k++)
if((a[i]>>k)&1)
b[k].insert(i);
q=queue<int>();
ans.clear();
for(int k=0;k<60;k++)
if(b[k].size()==2)
q.push(k);
while(!q.empty()){
ll i=*b[q.front()].begin(),j=*(--b[q.front()].end());
q.pop();
ans.push_back({i,a[i]&a[j]});
for(int k=0;k<60;k++){
if(((a[i]&a[j])>>k)&1){
b[k].erase(i);b[k].erase(j);
if(b[k].size()==2){
q.push(k);
}
}
}
}
if(ans.size()){
cout<<ans.size()<<endl;
for(auto t:ans)
cout<<t.first<<' '<<t.second<<endl;
}
else{
cout<<-1<<endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
input:
2 4 4 2 7 1 4 1 1 1 1
output:
3 3 1 2 2 1 4 -1
result:
ok OK 1 yes 1 no (2 test cases)
Test #2:
score: -100
Runtime Error
input:
50000 2 3 3 2 2 2 2 3 3 2 2 2 2 3 3 2 3 3 2 1 1 2 1 1 2 1 1 2 2 2 2 2 2 2 3 3 2 2 2 2 1 1 2 3 3 2 1 1 2 1 1 2 1 1 2 3 3 2 1 1 2 1 1 2 3 3 2 2 2 2 3 3 2 3 3 2 2 2 2 1 1 2 3 3 2 2 2 2 2 2 2 3 3 2 3 3 2 1 1 2 1 1 2 1 1 2 3 3 2 3 3 2 1 1 2 1 1 2 3 3 2 2 2 2 2 2 2 2 2 2 1 1 2 1 1 2 2 2 2 2 2 2 1 1 2 3 3 ...