QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#523494 | #9176. Non-Interactive Nim | ucup-team3282 | WA | 180ms | 3892kb | C++14 | 1.1kb | 2024-08-18 12:28:11 | 2024-08-18 12:28:13 |
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<int> b[61];
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 k=0;k<60;k++)
b[k].clear();
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()){
if(b[q.front()].empty()){
q.pop();
continue;
}
int 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: 3620kb
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: 0
Accepted
time: 44ms
memory: 3852kb
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 ...
output:
1 1 3 1 1 2 1 1 3 1 1 2 1 1 3 1 1 3 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 3 1 1 2 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 3 1 1 2 1 1 3 1 1 3 1 1 2 1 1 1 1 1 3 1 1 2 1 1 2 1 1 3 1 1 3 1 1 1 1 1 1 1 1 1 1 1 3 1 1 3 1 1 1 1 1 1 1 1 3 1 1 2 1 1 2 1 1 2 1 1 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 3 1 1 3 ...
result:
ok OK 50000 yes 0 no (50000 test cases)
Test #3:
score: -100
Wrong Answer
time: 180ms
memory: 3892kb
input:
50000 2 89846347117873058 89846347117873058 2 416235892302498917 416235892302498917 2 332154513003612985 332154513003612985 2 43960216631774959 43960216631774959 2 353215896487285554 353215896487285554 2 38296945667390613 38296945667390613 2 209150071115726640 209150071115726640 2 48610805835417777 ...
output:
1 1 -732706910 1 1 -1217049499 1 1 236948281 1 1 -2003431697 1 1 -2027597006 1 1 -2105754475 1 1 -1382432976 1 1 907069617 1 1 -1590423279 1 1 -184398503 1 1 1362194955 1 1 -538128596 1 1 -1851726319 1 1 1712060750 1 1 1654165883 1 1 -1342859856 1 1 -1453378331 1 1 401622420 1 1 -664206506 1 1 -2108...
result:
wrong answer Integer parameter [name=x] equals to -732706910, violates the range [1, 89846347117873058] (test case 1)