QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#523504#9176. Non-Interactive Nimucup-team3282WA 32ms3616kbC++141.1kb2024-08-18 12:32:292024-08-18 12:32:31

Judging History

你现在查看的是最新测评结果

  • [2024-08-18 12:32:31]
  • 评测
  • 测评结果:WA
  • 用时:32ms
  • 内存:3616kb
  • [2024-08-18 12:32:29]
  • 提交

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[65];
queue<int> q;
vector<pair<int,ll> >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]});
			a[i]^=(a[i]&a[j]);
			a[j]^=(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: 3616kb

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
Wrong Answer
time: 32ms
memory: 3584kb

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:

2
1 3
1 0
1
1 2
2
1 3
1 0
1
1 2
2
1 3
1 0
2
1 3
1 0
1
1 1
1
1 1
1
1 1
1
1 2
1
1 2
2
1 3
1 0
1
1 2
1
1 1
2
1 3
1 0
1
1 1
1
1 1
1
1 1
2
1 3
1 0
1
1 1
1
1 1
2
1 3
1 0
1
1 2
2
1 3
1 0
2
1 3
1 0
1
1 2
1
1 1
2
1 3
1 0
1
1 2
1
1 2
2
1 3
1 0
2
1 3
1 0
1
1 1
1
1 1
1
1 1
2
1 3
1 0
2
1 3
1 0
1
1 1
1
1 1
2
1 3
...

result:

wrong answer Integer parameter [name=x] equals to 0, violates the range [1, 0] (test case 1)