QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546976#1963. Squid Gameucup-team052#AC ✓0ms3956kbC++231.8kb2024-09-04 16:26:172024-09-04 16:26:19

Judging History

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

  • [2024-09-04 16:26:19]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3956kb
  • [2024-09-04 16:26:17]
  • 提交

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