QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546976 | #1963. Squid Game | ucup-team052# | AC ✓ | 0ms | 3956kb | C++23 | 1.8kb | 2024-09-04 16:26:17 | 2024-09-04 16:26:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
struct atom {
ll x;
int id;
atom (ll a = 0, int b = 0) : x(a), id(b) {}
bool operator < (const atom A) const {
return x < A.x;
}
bool operator > (const atom A) const {
return x > A.x;
}
bool operator == (const atom A) const {
return x == A.x;
}
};
vector <pii> ans;
atom a, b, c;
void gg() {
if ((int)ans.size() > 1000) return;
printf("%d\n", (int)ans.size());
for (auto i : ans) printf("%d %d\n", i.first, i.second);
exit(0);
}
void gao(atom &a, atom &b) {
assert(a.x >= b.x);
a.x -= b.x; b.x *= 2;
ans.emplace_back(a.id, b.id);
if (!a.x) gg();
}
void gaomod(atom &a, atom &b, atom &c) {
ll k = b.x / a.x;
for (int i = 0; k; i++) {
if ((k >> i) & 1) {
gao(b, a);
k ^= (1 << i);
} else {
gao(c, a);
}
}
}
mt19937 rng(0);
void solve(atom a, atom b, atom c) {
ans.clear();
for (int i = 1; i <= 50; i++) {
if (a > b) swap(a, b);
if (a > c) swap(a, c);
if (b > c) swap(b, c);
int x = rng() % 3;
if (x == 0) gao(b, a);
if (x == 1) gao(c, a);
if (x == 2) gao(c, b);
}
while ((int)ans.size() <= 1000) {
if (a > b) swap(a, b);
if (a > c) swap(a, c);
if (b > c) swap(b, c);
ll mn = 1e18; int id = 0;
ll x = b.x, y = c.x;
for (int i = 0; i <= 20; i++) {
ll now = (x < y ? x % a.x : y % a.x);
if (now < mn) {
mn = now; id = i;
}
if (x <= y) y -= x, x *= 2;
else x -= y, y *= 2;
}
for (int i = 1; i <= id; i++) {
if (b.x <= c.x) gao(c, b);
else gao(b, c);
}
if (b.x % a.x == mn) gaomod(a, b, c);
else gaomod(a, c, b);
}
}
int main() {
cin >> a.x >> b.x >> c.x;
a.id = 1; b.id = 2; c.id = 3;
while (1) {
solve(a, b, c);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3828kb
input:
1 2 3
output:
2 3 2 3 1
result:
ok good plan
Test #2:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
1 4 6
output:
16 3 2 3 1 2 1 1 3 2 3 3 1 1 3 1 3 3 1 2 3 1 2 2 1 2 3 3 2 1 2 1 2
result:
ok good plan
Test #3:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
3 4 8
output:
6 3 2 3 1 2 1 2 3 1 2 3 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
2 5 8
output:
32 3 2 3 1 2 1 2 3 1 3 2 3 3 2 3 2 1 2 3 1 2 1 1 2 1 3 3 1 2 1 2 3 1 2 1 2 3 2 3 1 2 3 3 2 3 2 2 1 2 1 1 2 2 3 2 1 1 3 3 1 2 3 1 3
result:
ok good plan
Test #5:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
3 8 12
output:
11 3 2 3 1 2 1 2 3 1 3 2 3 1 2 2 1 1 2 3 1 2 1
result:
ok good plan
Test #6:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
5 9 13
output:
16 3 2 1 3 2 3 2 1 3 1 2 1 3 2 2 1 1 2 3 2 1 2 2 1 2 3 3 2 1 3 3 2
result:
ok good plan
Test #7:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
4 15 26
output:
30 3 2 3 1 2 1 1 3 2 1 3 2 2 3 2 3 2 3 1 3 2 3 3 1 1 2 1 2 3 1 1 2 3 1 1 3 2 1 2 3 1 3 1 3 1 3 3 1 3 1 1 2 1 3 1 2 2 3 2 3
result:
ok good plan
Test #8:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
8 27 46
output:
58 3 2 3 1 2 1 1 3 2 1 3 2 1 3 1 3 2 3 1 2 3 2 2 1 1 3 3 1 2 3 2 1 3 2 3 2 1 2 1 3 2 1 1 3 1 3 3 1 1 2 1 2 1 3 2 1 3 2 2 3 1 2 3 2 1 2 1 3 2 3 1 2 2 1 2 3 3 2 3 1 3 2 3 1 2 1 2 3 2 1 1 3 3 1 3 1 3 1 1 3 1 2 2 1 2 1 1 2 1 2 3 2 1 2 3 2
result:
ok good plan
Test #9:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
27 35 43
output:
67 3 2 1 3 2 1 1 3 2 1 3 2 2 3 2 3 2 3 2 3 3 1 1 2 2 3 2 3 1 2 1 2 1 3 3 1 2 1 2 3 1 3 3 1 1 3 1 3 3 1 3 1 3 2 3 1 2 3 3 2 1 2 3 2 1 2 2 3 1 3 1 3 3 1 3 2 2 1 2 3 2 1 2 3 1 2 1 2 2 1 1 3 3 1 1 2 2 3 3 1 1 2 3 2 2 3 2 3 2 3 3 2 3 2 3 2 3 2 3 1 3 1 1 3 1 3 1 3 1 3 2 3 2 3
result:
ok good plan
Test #10:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
8 35 62
output:
67 3 2 3 1 2 3 3 1 2 3 1 2 2 1 2 1 2 1 2 1 1 3 3 2 2 1 2 1 3 2 3 2 3 1 1 3 2 3 2 1 3 1 1 3 3 1 3 1 1 3 1 3 1 2 1 3 2 1 1 2 3 2 1 2 3 2 2 1 3 1 3 1 1 3 1 2 2 3 2 1 2 3 2 1 3 2 3 2 2 3 3 1 1 3 3 2 2 1 1 3 3 2 1 2 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 3 1 3 3 1 3 1 3 1 3 1 2 1 2 1
result:
ok good plan
Test #11:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
66 95 98
output:
57 3 2 1 3 2 1 1 3 2 3 2 3 1 3 3 1 1 3 2 3 1 3 3 2 2 1 2 1 3 2 3 1 3 2 2 3 1 2 2 3 1 2 2 1 1 2 2 1 1 3 1 3 3 2 3 1 3 2 3 2 1 3 2 3 1 2 3 1 2 3 1 3 2 3 2 1 1 3 3 2 3 1 2 3 1 2 1 2 1 2 1 2 2 1 1 3 3 2 2 3 3 1 2 3 2 3 2 3 1 3 1 3 1 3
result:
ok good plan
Test #12:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
109 167 289
output:
63 3 2 3 1 2 1 2 3 1 3 2 3 1 2 1 2 1 3 2 1 1 3 3 1 1 2 1 2 3 1 3 2 1 3 3 1 2 3 3 1 2 3 3 1 3 1 3 1 1 2 1 2 1 3 1 2 3 1 1 3 2 3 1 3 2 1 1 3 2 3 1 3 2 1 2 3 3 1 3 2 1 3 2 1 3 2 3 1 3 2 2 1 1 2 1 3 3 2 2 3 2 1 1 2 2 3 1 3 2 3 3 2 2 1 3 1 2 1 3 1 3 1 2 1 3 1
result:
ok good plan
Test #13:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
269 380 398
output:
92 3 2 1 3 2 1 1 3 2 3 2 3 1 3 3 1 3 2 1 3 2 1 1 2 3 1 1 3 2 3 2 1 2 3 3 2 1 2 1 3 2 3 3 1 3 1 3 1 1 3 1 3 1 2 1 3 1 2 1 2 3 1 1 2 2 3 2 1 3 1 2 1 3 1 3 1 3 1 1 3 1 2 2 3 1 2 1 3 1 2 2 3 3 1 3 1 1 2 2 3 2 3 3 2 3 2 3 2 2 3 3 2 3 2 2 3 3 2 3 2 2 3 3 2 3 2 3 2 2 1 1 3 3 1 3 1 3 1 1 3 3 1 3 1 1 3 1 3 3...
result:
ok good plan
Test #14:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
233 364 480
output:
68 3 2 1 3 2 3 3 1 2 1 3 2 2 3 1 3 2 1 3 2 1 2 2 1 2 3 3 2 1 2 1 3 2 1 1 2 3 1 3 2 1 3 3 1 1 3 3 1 1 2 1 2 1 3 1 2 3 1 1 3 2 1 1 3 2 3 2 1 3 1 2 1 3 2 3 2 2 1 1 3 2 1 3 2 1 3 1 2 1 3 1 3 3 2 2 1 1 3 3 1 3 1 3 1 1 3 1 3 3 1 1 3 3 1 1 3 3 1 1 3 3 1 1 3 1 3 3 1 1 3 1 3 3 2 1 2
result:
ok good plan
Test #15:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
1098 1376 1489
output:
96 3 2 1 3 2 1 2 3 1 3 1 3 3 1 2 3 3 2 1 2 3 2 2 3 3 1 1 3 2 1 2 3 1 2 2 1 3 1 1 2 3 1 1 3 3 2 3 2 2 3 3 2 3 1 3 2 1 3 3 1 2 1 1 3 2 3 1 2 3 2 2 1 3 2 3 1 1 3 3 2 3 2 3 1 2 3 2 3 2 3 2 1 1 3 1 2 1 2 2 1 2 1 1 2 1 2 1 2 2 1 1 2 1 2 2 1 2 1 2 1 2 3 1 3 3 1 3 1 1 3 3 1 3 1 3 1 1 3 3 1 1 3 3 2 3 2 3 2 3...
result:
ok good plan
Test #16:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
10035 10338 10444
output:
105 3 2 1 3 2 1 2 3 1 3 2 3 1 3 1 3 1 3 2 1 1 3 3 2 2 1 1 2 3 1 3 2 2 1 2 1 3 2 3 1 2 3 3 2 2 1 1 2 2 3 2 3 3 1 3 1 1 2 2 1 3 2 1 2 3 2 3 1 2 3 1 3 2 3 3 2 2 1 1 3 1 2 3 1 2 3 2 3 2 3 2 3 2 1 2 1 2 1 1 2 1 3 1 3 3 1 3 1 3 1 3 1 3 1 1 3 3 1 3 1 1 3 3 1 1 3 1 3 1 3 3 1 1 3 3 1 3 1 1 2 3 2 1 2 3 2 2 3 ...
result:
ok good plan
Test #17:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
100010 100200 100227
output:
92 3 2 1 3 2 1 2 3 1 3 2 3 1 3 1 3 1 3 2 3 1 2 2 1 2 3 2 3 1 3 1 2 1 3 3 1 2 1 3 2 1 2 2 1 2 1 1 2 1 2 1 2 1 3 1 2 1 3 3 1 2 3 3 1 2 1 1 3 2 3 1 3 3 1 3 2 2 3 2 1 2 3 1 2 3 1 3 1 3 1 3 2 2 3 3 1 1 2 2 1 2 3 3 1 2 1 1 3 1 3 3 1 3 1 1 3 3 1 3 1 3 1 1 3 3 1 1 2 3 2 1 2 3 2 3 2 1 2 3 2 3 2 2 3 2 3 2 3 3...
result:
ok good plan
Test #18:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
1000000 1000235 1000288
output:
126 3 2 1 3 2 1 2 3 1 3 2 3 1 3 1 3 1 3 2 3 1 2 2 1 2 3 2 3 1 3 1 2 1 3 1 3 2 1 2 3 1 3 3 2 2 3 3 2 3 2 2 1 2 3 2 1 2 3 2 3 1 2 3 2 1 2 1 3 2 1 1 3 2 1 2 3 3 2 3 1 3 2 3 1 2 3 3 2 2 3 3 1 1 2 1 3 3 2 2 3 2 3 1 3 2 3 3 2 3 2 2 3 3 2 2 3 2 3 2 3 2 3 3 2 3 2 3 2 3 2 2 1 3 1 2 1 2 1 2 1 2 1 3 1 1 2 2 3 ...
result:
ok good plan
Test #19:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
10000011 10000314 10000358
output:
148 3 2 1 3 2 1 2 3 1 3 2 3 1 3 1 3 1 3 2 3 1 2 2 1 2 3 2 3 1 3 1 2 1 3 1 3 2 1 2 3 1 2 2 1 1 2 2 1 1 2 2 1 1 3 1 2 3 1 1 3 2 3 1 3 2 1 1 3 2 3 1 3 2 1 2 3 2 3 3 1 3 2 3 1 2 3 1 3 3 1 3 2 2 3 2 3 3 2 2 3 3 2 2 3 2 3 2 3 3 2 2 3 3 1 1 3 3 1 3 1 3 1 3 1 3 1 3 2 1 2 3 2 3 2 1 2 2 1 1 2 2 1 1 2 1 2 1 2 ...
result:
ok good plan
Test #20:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
100000057 100000244 100000402
output:
184 3 2 1 3 2 1 2 3 1 3 2 3 1 3 1 3 1 3 2 3 1 2 2 1 2 3 2 3 1 3 1 2 1 3 1 3 2 1 2 3 1 2 2 1 1 2 2 1 1 2 2 1 1 3 1 2 1 3 1 3 2 3 1 3 2 3 2 1 3 1 2 1 3 2 1 2 2 3 3 1 3 2 3 1 2 3 2 3 2 3 3 2 2 3 2 3 2 3 3 2 3 1 1 3 1 3 3 1 3 1 3 1 3 1 1 3 3 2 2 3 3 2 3 2 3 2 2 1 2 1 2 1 2 1 3 1 3 1 1 3 3 1 3 2 3 2 1 2 ...
result:
ok good plan
Test #21:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
1 1000000 1000000000
output:
183 3 2 2 1 3 2 2 1 3 1 2 1 3 1 3 1 3 1 2 1 3 2 3 2 2 1 2 1 3 1 3 2 2 1 2 1 3 2 2 1 3 2 3 2 3 2 2 3 3 2 3 2 3 1 3 2 2 1 2 1 3 1 2 1 3 2 2 1 3 1 2 1 3 1 3 2 2 3 3 1 3 2 3 1 2 1 2 1 2 3 2 3 2 1 2 1 1 3 3 2 3 2 2 3 3 2 3 2 3 1 2 1 1 2 1 2 2 1 2 1 1 2 2 1 2 1 1 2 1 2 1 3 1 3 2 3 2 3 2 3 3 2 3 2 2 3 2 3 ...
result:
ok good plan
Test #22:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
1024 65536 536870912
output:
128 3 2 2 1 3 2 2 1 3 1 2 1 3 1 3 1 3 1 2 1 3 1 3 1 1 2 1 2 3 2 3 2 2 1 1 2 3 2 2 1 3 2 3 2 3 2 3 2 3 2 3 2 2 1 2 3 2 1 2 1 3 1 2 1 3 2 2 1 3 1 2 1 3 2 3 2 3 2 2 3 2 3 2 1 3 2 3 2 2 3 3 1 1 3 1 2 2 1 1 2 1 3 3 1 1 3 1 3 3 1 3 1 1 3 1 3 1 3 1 3 1 3 1 3 3 1 3 1 1 2 3 2 1 2 2 1 1 2 1 2 2 1 2 1 2 1 2 1 ...
result:
ok good plan
Test #23:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
6 268435456 536870912
output:
110 3 2 3 1 2 3 2 1 3 1 2 1 3 1 3 1 3 1 2 1 3 2 2 3 2 1 2 1 3 1 3 2 3 1 3 1 2 3 2 1 3 2 2 3 3 2 2 3 3 2 2 3 3 1 3 2 3 1 3 1 2 1 3 1 2 3 2 1 3 1 2 1 3 1 3 2 2 3 3 1 3 2 3 1 2 3 2 3 2 1 1 3 3 1 3 2 2 1 1 2 1 3 3 1 1 3 1 3 3 1 3 1 3 1 1 3 3 2 1 2 3 2 1 2 1 2 3 2 1 2 3 2 1 2 3 2 3 2 1 2 3 2 1 2 3 2 1 2 ...
result:
ok good plan
Test #24:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
7 16777217 536870909
output:
174 3 2 2 1 3 2 2 1 3 1 2 1 3 1 3 1 3 1 2 1 3 2 3 2 2 1 2 1 3 1 3 2 3 1 3 1 2 3 3 1 2 3 2 3 2 3 2 3 3 2 3 2 3 1 3 2 2 1 2 1 3 1 2 1 3 2 3 1 2 1 3 1 2 1 2 3 3 1 3 2 3 1 1 2 3 2 2 3 3 2 3 1 1 2 1 2 1 3 3 2 2 3 3 2 3 2 2 3 3 2 3 2 2 1 2 1 1 2 1 2 1 2 1 2 1 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1 3 2 3 ...
result:
ok good plan
Test #25:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
24223 44594 72242
output:
104 3 2 3 1 2 1 2 3 1 3 2 3 1 2 1 3 3 1 2 3 1 3 3 1 2 3 3 2 1 3 1 3 1 2 2 1 3 2 3 1 2 1 2 1 1 3 1 3 1 3 1 3 3 2 3 1 3 2 3 2 1 3 3 2 1 2 1 3 2 1 3 1 2 3 2 3 3 2 2 1 2 1 3 2 1 2 1 2 2 3 3 1 1 2 1 3 3 1 1 3 1 2 2 1 1 2 1 2 2 1 2 1 2 1 2 1 1 2 2 1 2 1 1 3 1 3 1 3 3 1 1 2 3 2 1 2 1 2 1 2 1 2 1 2 1 2 2 1 ...
result:
ok good plan
Test #26:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
123441 146831 150393
output:
135 3 2 1 3 2 1 2 3 1 3 2 3 1 3 1 3 3 1 2 1 1 3 3 1 1 2 1 2 3 1 3 2 3 1 3 1 2 3 2 1 3 2 3 2 3 2 2 1 2 1 2 1 1 3 1 2 1 3 3 1 2 3 1 3 2 3 1 2 3 1 1 2 3 1 3 2 3 2 2 1 2 3 1 2 3 1 3 2 2 1 1 3 3 2 3 1 3 1 1 3 1 3 3 1 3 1 3 1 3 1 1 3 1 3 3 1 1 3 1 3 3 1 3 1 1 3 3 2 2 3 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 3 ...
result:
ok good plan
Test #27:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
1017604 1044219 1047264
output:
110 3 2 1 3 2 1 2 3 1 3 2 3 1 3 1 3 1 3 2 3 1 3 3 1 3 2 2 3 1 3 1 2 1 3 1 3 2 1 1 3 2 1 2 1 1 2 1 2 2 1 1 2 2 3 1 2 3 1 3 1 2 1 3 1 2 1 1 3 2 3 3 1 1 3 1 2 2 1 2 3 2 1 1 3 2 3 2 3 2 3 2 1 1 3 1 3 3 1 1 3 1 2 1 2 2 3 2 3 2 3 3 2 3 2 3 2 3 2 2 1 2 1 2 1 2 1 3 1 3 1 2 1 1 2 1 2 1 2 2 1 2 1 1 2 1 2 2 1 ...
result:
ok good plan
Test #28:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
10023437 10049857 10053253
output:
165 3 2 1 3 2 1 2 3 1 3 2 3 1 3 1 3 1 3 2 3 1 2 2 1 2 3 2 3 1 3 1 3 1 2 2 1 3 2 1 3 2 3 3 2 2 3 2 3 2 3 3 2 3 1 2 3 1 2 1 2 3 2 1 2 3 2 2 1 3 1 2 1 3 2 3 1 1 2 1 3 2 1 3 2 1 3 1 2 1 3 3 2 2 3 2 3 2 1 2 3 1 2 2 1 2 1 2 1 2 1 1 2 2 1 2 1 1 2 2 1 1 3 3 2 2 3 3 1 2 1 2 1 2 1 3 1 1 3 2 3 2 3 1 3 2 3 1 3 ...
result:
ok good plan
Test #29:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
100010076 100034479 100039408
output:
186 3 2 1 3 2 1 2 3 1 3 2 3 1 3 1 3 1 3 2 3 1 2 2 1 2 3 2 3 1 3 1 2 1 3 1 3 2 1 2 3 1 3 3 2 2 3 3 2 2 3 3 2 2 1 1 3 2 1 2 1 3 2 2 1 3 1 3 2 1 3 3 2 1 3 1 2 2 3 3 1 3 2 1 3 2 1 2 3 3 2 2 1 1 2 1 2 2 3 3 1 1 3 3 1 3 1 1 3 1 3 1 3 3 1 3 1 1 3 3 1 3 1 3 1 1 3 1 3 3 1 1 2 1 2 2 1 2 1 2 1 2 1 2 1 2 1 1 3 ...
result:
ok good plan
Test #30:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
100021199 100049225 100065369
output:
168 3 2 1 3 2 1 2 3 1 3 2 3 1 3 1 3 1 3 2 3 1 2 2 1 2 3 2 3 1 3 1 2 1 3 1 3 2 3 2 1 3 2 3 2 3 2 2 3 2 3 3 2 2 1 2 3 3 1 3 1 2 3 3 1 2 1 1 3 2 3 1 3 2 1 3 2 2 1 1 3 2 1 3 2 1 2 1 3 1 2 1 2 2 3 1 2 2 3 3 1 3 2 2 3 3 2 2 3 3 2 3 2 3 2 3 2 2 3 3 2 3 2 3 2 2 1 3 1 2 1 2 1 1 2 2 1 1 2 1 2 1 2 2 1 2 1 1 2 ...
result:
ok good plan