QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#328236 | #8041. Life is Hard and Undecidable, but... | PetroTarnavskyi# | AC ✓ | 2ms | 3860kb | C++20 | 1.8kb | 2024-02-15 18:28:48 | 2024-02-15 18:28:48 |
Judging History
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