QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#514497 | #9176. Non-Interactive Nim | ucup-team3695# | RE | 12ms | 3824kb | C++20 | 1.3kb | 2024-08-11 02:21:20 | 2024-08-11 02:21:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int hp(int x){
int i = 0;
while((1ll<<i) <= x)i++;
return i;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int tests;cin>>tests;
while(tests--){
int n;cin>>n;
vi a(n);rep(i,0,n)cin>>a[i];
if(n>200){
cout<<-1<<endl;
continue;
}
vi inds(n);iota(all(inds),0);
sort(all(inds),[&](int i, int j){ return a[i]>a[j];});
// rep(i,0,n)cout<<a[inds[i]]<<' ';
// cout<<'\n';
vector<pii> ops;
bool bad = false;
while(sz(inds)){
if(sz(inds)>2 && hp(a[inds[0]])==hp(a[inds[2]])){
bad=true;
break;
}
// rep(i,0,sz(inds))cout<<a[inds[i]]<<' ';
// cout<<'\n';
// cout<<"xor by "<<a[inds[1]]<<endl;
ops.pb({inds[0],a[inds[0]]-(a[inds[0]]^a[inds[1]])});
a[inds[0]]^=a[inds[1]];
inds.erase(inds.begin()+1);
if(a[inds[0]]==0)inds.erase(inds.begin());
sort(all(inds),[&](int i, int j){ return a[i]>a[j];});
}
if(bad)cout<<"-1\n";
else{
cout<<sz(ops)<<'\n';
for(pii op : ops)cout<<op.F+1<<' '<<op.S<<'\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
input:
2 4 4 2 7 1 4 1 1 1 1
output:
3 3 4 3 2 3 1 -1
result:
ok OK 1 yes 1 no (2 test cases)
Test #2:
score: 0
Accepted
time: 12ms
memory: 3528kb
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
Runtime Error
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 ...