QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#523494#9176. Non-Interactive Nimucup-team3282WA 180ms3892kbC++141.1kb2024-08-18 12:28:112024-08-18 12:28:13

Judging History

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

  • [2024-08-18 12:28:13]
  • 评测
  • 测评结果:WA
  • 用时:180ms
  • 内存:3892kb
  • [2024-08-18 12:28:11]
  • 提交

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)