QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#686794 | #9176. Non-Interactive Nim | ucup-team4975# | TL | 17ms | 3568kb | C++23 | 1.6kb | 2024-10-29 15:43:36 | 2024-10-29 15:43:36 |
Judging History
answer
#define LOCAL
#include <bits/stdc++.h>
#define fir first
#define sec second
#define el '\n'
#define int long long
#ifdef LOCAL
#define FINISH cerr << "FINISH" << endl;
#else
#define FINISH ;
#endif
#ifdef LOCAL
#define debug(x) cerr << setw(4) << #x << " == " << x << endl
#else
#define debug(x)
#endif
#ifdef LOCAL
#define debugv(x) \
cerr << setw(4) << #x << ":: "; \
for (auto i : x) \
cerr << i << " "; \
cerr << endl
#else
#define debugv(x)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
ostream& operator<<(ostream& out, PII& x)
{
out << x.fir << " " << x.sec << endl;
return out;
}
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int N = 200020;
void solve()
{
int n;
cin >> n;
vector<PII> a(n + 5, {0, 0});
for (int i = 1; i <= n; i++) {
cin >> a[i].fir;
a[i].sec = i;
}
vector<PII> ans;
while (1) {
sort(next(a.begin()), a.end(),
[&](PII x, PII y) { return x.fir > y.fir; });
if (a[1].fir == 0)
break;
int high = -1;
for (ll j = 60; j >= 0; j--) {
if (a[1].fir >> j & 1) {
high = j;
break;
}
}
if (a[3].fir >> high & 1) {
cout << "-1" << el;
return;
}
ll now = (1 << high);
ans.push_back(PII(a[1].sec, now));
a[1].fir -= now, a[2].fir -= now;
}
cout << ans.size() << el;
for (auto [x, y] : ans) {
cout << x << " " << y << el;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3568kb
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: 17ms
memory: 3508kb
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 2 1 1 1 1 2 2 1 2 1 1 1 1 2 2 1 2 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 2 1 2 1 1 1 1 2 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 2 2 1 2 1 1 2 1 2 1 1 1 1 2 1 1 1 2 1 2 1 1 1 1 2 1 1 2 2 1 2 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 2 1 2 1 1 1 1 1 1 1 1 2 1 2 ...
result:
ok OK 50000 yes 0 no (50000 test cases)
Test #3:
score: -100
Time Limit Exceeded
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 ...