QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#328236#8041. Life is Hard and Undecidable, but...PetroTarnavskyi#AC ✓2ms3860kbC++201.8kb2024-02-15 18:28:482024-02-15 18:28:48

Judging History

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

  • [2024-02-15 18:28:48]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3860kb
  • [2024-02-15 18:28:48]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;


vector<vector<PII>> res;
int solve(vector<PII> v, int t)
{
	int cnt = 0;
	while (cnt < 1000 && !v.empty())
	{
		
		if(t == 1)
			res.PB(v);	
			
		set<PII> cand;
		FOR (i, 0, SZ(v))
		{
			FOR (dx, -1, 2)
			{
				FOR (dy, -1, 2)
					cand.insert({v[i].F + dx, v[i].S + dy});
			}
		}
		vector<PII> nv;
		for (auto p : cand)
		{
			int susids = 0;
			bool alive = false;
			FOR (i, 0, SZ(v))
			{
				if (p == v[i])
				{
					alive = 1;
					continue;
				}
				int dx = abs(p.F - v[i].F);
				int dy = abs(p.S - v[i].S);
				int mx = max(dx, dy);
				int d = dx + dy;
				if (mx < 2 && d <= 2)
					susids++;
			}
			if (susids == 3 || (susids == 2 && alive))
				nv.PB(p);
		}
		v = nv;
		cnt++;	
			
	}
	return cnt;
}

vector<PII> solution(int k)
{
	if(k <= SZ(res))
	{
		return res[SZ(res) - k];
	}
	assert(0);
}


const int N = 74;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	vector<PII> cur = {MP(0, 2), MP(1, 0), MP(1, 2), MP(2, 1), MP(2, 2),
	MP(N + 5, N + 3), MP(N + 5, N + 4), MP(N + 6, N + 3), MP(N + 6, N + 4)};
	
	cerr << solve(cur, 1) << endl;
		
	int k;
	cin >> k;
	vector<PII> ans = solution(k);
		
	
	cout << SZ(ans) << "\n";
	FOR(i, 0, SZ(ans))
	{
		ans[i].F++;
		ans[i].S++;
		cout << ans[i].F << " " << ans[i].S << "\n";
	}
	
	assert(solve(ans, 0) == k);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3648kb

input:

1

output:

2
73 76
73 77

result:

ok n=2

Test #2:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

2

output:

3
72 77
73 76
74 77

result:

ok n=3

Test #3:

score: 0
Accepted
time: 2ms
memory: 3844kb

input:

3

output:

5
72 77
72 78
73 76
74 77
74 78

result:

ok n=5

Test #4:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

4

output:

5
72 77
72 78
73 77
73 78
74 77

result:

ok n=5

Test #5:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

5

output:

6
72 77
72 78
73 76
73 79
75 76
75 78

result:

ok n=6

Test #6:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

6

output:

9
72 78
73 77
73 78
74 76
74 77
74 78
75 76
75 77
76 82

result:

ok n=9

Test #7:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

7

output:

11
72 78
73 77
73 79
74 76
75 77
75 81
76 77
76 82
77 83
79 78
80 81

result:

ok n=11

Test #8:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

8

output:

28
73 77
73 78
73 79
74 77
74 78
74 79
75 77
75 78
75 79
75 80
76 79
76 81
76 82
77 78
77 79
77 81
77 82
78 74
78 75
78 78
78 79
78 80
78 81
78 82
79 79
79 80
79 81
80 81

result:

ok n=28

Test #9:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

9

output:

19
73 78
74 77
74 78
74 79
75 76
75 80
76 81
77 74
77 78
77 79
77 81
77 82
78 78
78 79
79 74
79 75
79 82
80 80
80 81

result:

ok n=19

Test #10:

score: 0
Accepted
time: 1ms
memory: 3860kb

input:

10

output:

24
74 77
74 78
74 79
75 76
75 80
76 76
76 77
76 79
76 80
77 75
77 76
77 78
77 79
77 81
78 74
78 75
78 81
78 82
79 74
79 75
79 79
79 81
79 82
80 80

result:

ok n=24

Test #11:

score: 0
Accepted
time: 1ms
memory: 3856kb

input:

13

output:

17
75 78
76 77
76 78
76 79
77 76
77 77
77 80
78 75
78 76
78 79
78 80
78 81
79 74
79 75
79 76
79 80
81 78

result:

ok n=17

Test #12:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

17

output:

14
77 77
77 78
77 79
78 77
78 78
78 79
79 77
79 78
79 80
80 76
80 78
80 79
81 77
81 78

result:

ok n=14

Test #13:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

23

output:

10
76 78
77 77
77 79
78 76
78 77
78 79
79 76
80 77
80 79
81 78

result:

ok n=10

Test #14:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

29

output:

9
75 77
76 78
77 76
77 77
77 78
80 78
80 79
81 78
81 79

result:

ok n=9

Test #15:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

31

output:

9
75 77
76 75
76 77
77 76
77 77
80 78
80 79
81 78
81 79

result:

ok n=9

Test #16:

score: 0
Accepted
time: 2ms
memory: 3640kb

input:

37

output:

9
73 75
74 76
75 74
75 75
75 76
80 78
80 79
81 78
81 79

result:

ok n=9

Test #17:

score: 0
Accepted
time: 2ms
memory: 3572kb

input:

41

output:

9
72 74
73 75
74 73
74 74
74 75
80 78
80 79
81 78
81 79

result:

ok n=9

Test #18:

score: 0
Accepted
time: 2ms
memory: 3800kb

input:

43

output:

9
72 74
73 72
73 74
74 73
74 74
80 78
80 79
81 78
81 79

result:

ok n=9

Test #19:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

100

output:

9
58 58
58 60
59 59
59 60
60 59
80 78
80 79
81 78
81 79

result:

ok n=9

Test #20:

score: 0
Accepted
time: 2ms
memory: 3528kb

input:

85

output:

9
61 63
62 64
63 62
63 63
63 64
80 78
80 79
81 78
81 79

result:

ok n=9

Test #21:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

97

output:

9
58 60
59 61
60 59
60 60
60 61
80 78
80 79
81 78
81 79

result:

ok n=9

Test #22:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

98

output:

9
58 59
59 60
59 61
60 59
60 60
80 78
80 79
81 78
81 79

result:

ok n=9

Test #23:

score: 0
Accepted
time: 2ms
memory: 3560kb

input:

99

output:

9
58 60
59 58
59 60
60 59
60 60
80 78
80 79
81 78
81 79

result:

ok n=9

Extra Test:

score: 0
Extra Test Passed