QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#140916#6305. Chinese CheckersupepapupuAC ✓29ms3556kbC++172.5kb2023-08-16 23:19:222023-08-16 23:19:24

Judging History

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

  • [2023-08-16 23:19:24]
  • 评测
  • 测评结果:AC
  • 用时:29ms
  • 内存:3556kb
  • [2023-08-16 23:19:22]
  • 提交

answer

#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 3e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

inline int read() {
    int f = 1, k = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        k = k * 10 + c - '0';
        c = getchar();
    }
    return f * k;
}

int n;
ll ans;
vector<pii> q;
set<pii> S;
int L[] = {0, 5, 5, 5, 5, 1, 2, 3, 4, 5, 5, 5, 5, 5, 10, 11, 12, 13};
int R[] = {0, 5, 6, 7, 8, 13, 13, 13, 13, 13, 14, 15, 16, 17, 13, 13, 13, 13};

void bfs(int u) {
    set<pii> st;
    queue<pii> Q;
    st.insert(q[u]);
    Q.push(q[u]);
    while (Q.size()) {
        auto[x, y] = Q.front();
        Q.pop();
        auto get = [&](int p)->pii {
            auto[a, b] = q[p];
            int dx = a - x, dy = b - y;
            pii fail = {-1, -1};
            if (dx && dy && dx != dy) return fail;
            pii res = {a + dx, b + dy};
            if (res.x <= 0 || res.x > 17) return fail;
            if (res.y < L[res.x] || res.y > R[res.x]) return fail;
            if (S.count(res)) return fail;
            if (dx) dx = dx > 0 ? 1 : -1;
            if (dy) dy = dy > 0 ? 1 : -1;
            for (int i = x + dx, j = y + dy; i != res.x || j != res.y; i += dx, j += dy) {
                if (i == q[u].x && j == q[u].y) continue;
                if (i == a && j == b) continue;
                if (S.count({i, j})) return fail;
            }
            return res;
        };

        for (int i = 0; i < n; ++i) {
            if (i == u) continue;
            auto[a, b] = get(i);
            if (~a) {
                if (!st.count({a, b})) {
                    st.insert({a, b});
                    Q.push({a, b});
                }
            }
        }
    }
    // cout << st.size() << el;
    // for (auto[a, b]: st) cout << a << ' ' << b - L[a] + 1 << el;
    ans += st.size() - 1;
}

void solve() {
    n = read();
    q.clear();
    S.clear();
    for (int i = 0; i < n; ++i) {
        int x = read(), y = read();
        y += L[x] - 1;
        q.emplace_back(x, y);
        S.insert({x, y});
    }
    ans = 0;
    for (int i = 0; i < n; ++i) {
        bfs(i);
    }
    cout << ans << el;
}

int main() {
    int tcase;
    cin >> tcase;
    while (tcase--) solve();
}

详细

Test #1:

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

input:

5
1
1 1
2
1 1
2 1
2
9 4
9 6
10
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4
10
1 1
2 1
2 2
5 7
3 2
3 3
4 1
4 2
4 3
4 4

output:

0
1
2
6
13

result:

ok 5 number(s): "0 1 2 6 13"

Test #2:

score: 0
Accepted
time: 19ms
memory: 3556kb

input:

100
81
1 1
16 1
11 4
13 8
12 3
12 12
11 1
4 2
9 5
8 10
5 5
9 7
3 2
14 1
7 11
13 7
10 2
8 3
9 8
10 6
12 10
6 7
11 2
7 3
13 12
8 6
17 1
10 5
5 12
13 9
13 1
9 4
5 10
11 8
13 4
5 4
9 1
7 8
5 6
13 13
5 1
9 3
8 8
8 5
13 2
13 5
11 3
9 2
6 4
3 3
8 2
13 11
8 7
5 7
6 10
11 9
10 3
11 10
6 3
7 1
4 4
15 2
7 2
3 ...

output:

190
376
211
492
381
228
151
39
328
87
1
141
103
65
25
137
394
294
10
214
91
188
263
16
102
236
304
443
172
84
218
281
25
7
104
181
429
282
51
163
276
47
10
164
79
181
30
145
333
122
200
291
0
105
115
54
22
5
62
159
167
26
447
163
209
4
52
0
251
109
100
405
0
348
75
105
75
353
66
28
474
362
6
190
90
...

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 15ms
memory: 3508kb

input:

100
38
6 11
13 8
7 2
7 4
11 3
12 1
7 6
6 3
4 2
5 1
12 8
10 3
12 4
10 7
15 3
14 4
3 1
5 12
6 12
10 10
13 7
8 6
15 2
15 1
7 5
5 5
8 3
12 3
4 1
7 3
1 1
5 9
8 10
11 6
11 1
11 11
16 2
9 5
46
11 9
10 4
8 6
12 10
11 1
6 8
6 3
7 10
6 6
12 3
9 7
10 1
14 4
12 9
6 1
5 3
7 8
8 4
6 5
5 2
14 2
9 1
6 7
3 3
7 3
11 ...

output:

369
402
268
186
336
29
31
295
421
434
38
1
3
228
271
56
139
316
20
49
176
265
515
176
258
294
258
134
445
7
7
47
311
149
283
276
102
169
247
17
226
512
24
231
101
324
0
0
56
156
160
23
99
0
58
266
170
51
2
443
15
3
58
322
21
31
276
3
164
311
57
21
120
250
198
318
30
151
342
59
277
75
347
198
322
73
...

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 18ms
memory: 3512kb

input:

100
67
11 11
7 9
10 1
13 7
16 2
11 7
5 6
12 9
12 11
10 9
11 9
13 4
5 5
4 1
6 5
7 2
13 3
13 11
5 8
2 2
6 7
14 3
7 10
12 4
13 12
12 1
4 3
16 1
10 4
8 9
5 10
5 1
13 10
4 4
6 1
13 2
11 8
5 7
8 10
11 10
13 13
6 2
6 10
7 8
8 4
6 8
9 3
6 12
8 2
14 4
12 10
3 1
7 4
4 2
8 7
7 6
7 1
5 12
5 11
3 3
5 9
6 11
11 1...

output:

319
301
374
170
318
2
1
249
112
389
173
59
201
409
148
163
0
256
383
466
46
440
447
264
281
67
306
293
201
252
583
226
15
67
0
33
83
5
4
95
41
74
202
25
112
29
279
203
332
243
59
45
225
39
0
83
321
234
409
172
256
194
1
94
1
106
50
9
204
18
342
37
12
262
72
167
4
53
125
348
12
0
4
101
3
65
290
97
14...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 18ms
memory: 3508kb

input:

100
23
6 9
3 1
1 1
7 3
8 10
13 9
7 10
11 4
8 4
13 7
5 4
9 7
7 11
8 6
11 2
11 6
10 5
12 10
15 1
13 5
5 1
7 5
6 10
82
6 2
3 3
11 5
10 2
12 1
7 2
5 3
8 6
7 9
2 2
10 7
10 10
10 8
6 8
8 3
12 10
11 9
9 7
5 1
8 10
13 4
6 6
1 1
5 2
13 13
7 8
7 10
17 1
11 1
12 12
6 1
13 6
14 2
15 1
13 8
12 9
12 6
6 3
16 2
9 ...

output:

189
217
8
326
256
407
168
315
97
260
94
141
53
0
117
294
149
200
278
182
300
407
71
186
306
46
175
81
82
59
156
162
539
0
143
306
0
5
2
0
0
127
32
453
159
238
135
11
0
21
38
12
51
128
162
187
19
428
372
127
0
149
0
33
0
11
188
172
186
2
26
99
46
128
310
14
252
186
182
269
279
282
166
246
194
70
29
2...

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 17ms
memory: 3512kb

input:

100
52
5 11
5 4
9 5
8 5
5 2
8 7
17 1
13 9
7 3
11 9
6 6
9 7
12 9
8 3
10 3
6 4
8 8
10 7
9 1
7 2
15 2
7 9
11 10
3 3
7 1
4 2
13 2
12 2
4 3
5 7
5 3
6 3
8 6
11 3
3 2
7 5
7 10
11 2
3 1
11 8
11 7
13 13
7 8
16 2
16 1
10 1
7 7
13 3
9 3
6 2
12 1
6 7
77
5 9
9 3
14 4
12 7
13 1
6 6
7 8
8 5
5 13
9 2
11 10
12 12
1 ...

output:

268
194
131
20
174
379
10
204
296
58
43
304
4
26
298
96
41
279
106
238
274
20
121
10
235
145
1
250
0
36
24
57
147
86
172
221
222
354
57
349
5
50
317
360
8
8
271
233
5
403
263
291
428
4
73
30
306
85
239
42
196
267
24
2
221
20
335
365
93
423
333
5
134
17
0
6
245
213
112
252
51
274
288
57
126
24
322
17...

result:

ok 100 numbers

Test #7:

score: 0
Accepted
time: 27ms
memory: 3508kb

input:

100
50
11 5
8 6
12 7
14 4
8 4
6 6
7 10
13 2
10 9
13 12
12 1
10 2
6 8
14 1
15 3
3 1
5 6
13 10
5 10
10 10
5 3
7 4
11 4
9 3
11 9
11 1
9 7
12 10
17 1
7 6
4 4
12 8
13 7
8 2
8 7
9 6
8 1
8 8
12 2
3 3
5 1
15 1
12 5
10 3
7 9
9 9
1 1
14 2
10 8
5 5
50
12 7
11 4
8 2
9 4
16 2
9 3
4 2
5 6
4 4
6 2
11 10
3 2
7 7
5 ...

output:

403
352
337
347
289
335
286
344
311
297
352
504
343
271
229
288
280
262
375
380
410
308
285
241
349
313
503
458
370
316
282
377
249
340
332
269
320
369
352
367
316
384
349
288
398
294
274
230
225
247
253
256
326
437
290
306
238
265
302
333
524
330
338
478
262
234
278
353
456
351
292
500
392
284
261
...

result:

ok 100 numbers

Test #8:

score: 0
Accepted
time: 25ms
memory: 3504kb

input:

100
55
6 3
11 6
11 5
8 6
15 3
7 3
13 4
11 11
12 7
5 4
7 5
9 6
11 1
13 6
9 1
12 2
13 1
3 3
8 8
5 6
11 3
14 3
8 10
1 1
10 3
10 6
14 4
6 7
13 3
7 7
5 13
10 4
11 8
17 1
12 6
11 7
14 1
10 10
6 10
8 2
8 5
16 2
5 3
13 5
13 11
8 1
7 6
6 1
3 1
7 10
7 2
5 9
6 6
10 2
10 1
55
7 4
10 8
13 1
8 3
12 4
4 2
11 9
6 1...

output:

297
273
256
378
387
300
311
350
397
302
333
403
262
508
317
363
276
438
452
251
606
288
200
221
449
278
404
457
315
276
410
307
327
296
291
358
341
367
371
309
269
413
338
340
490
372
360
295
386
316
440
267
280
333
342
230
338
366
311
231
210
496
412
417
300
235
428
207
239
405
285
476
391
282
382
...

result:

ok 100 numbers

Test #9:

score: 0
Accepted
time: 29ms
memory: 3500kb

input:

100
60
6 7
2 2
7 5
10 3
8 1
12 10
9 6
10 6
13 1
9 2
12 2
13 10
15 1
8 10
15 2
10 1
5 1
5 2
5 10
12 1
7 11
3 3
12 4
7 2
9 5
7 6
11 6
5 12
13 2
13 5
10 5
7 9
3 1
16 1
10 4
4 2
9 3
12 11
1 1
11 7
9 4
10 2
5 5
13 8
5 7
6 3
3 2
13 13
12 12
16 2
8 3
7 10
8 5
13 6
14 2
10 9
6 6
9 8
6 5
10 7
60
13 13
3 1
10...

output:

263
221
365
327
230
235
317
302
306
373
220
274
273
333
333
395
418
350
309
215
230
327
265
373
435
433
286
274
218
301
326
252
456
300
365
354
355
463
252
354
366
394
274
246
306
287
289
374
275
391
380
380
265
280
306
380
395
339
345
333
321
196
307
382
255
248
305
302
363
285
291
290
238
267
264
...

result:

ok 100 numbers

Test #10:

score: 0
Accepted
time: 16ms
memory: 3460kb

input:

100
121
12 1
5 1
3 2
13 6
8 10
10 5
6 9
4 2
13 8
16 1
7 10
7 1
11 5
10 8
10 2
12 7
15 3
13 5
1 1
5 12
17 1
5 2
13 11
9 6
8 4
6 2
11 4
11 10
14 2
4 3
12 3
6 12
4 1
7 6
13 13
10 10
5 11
5 13
6 1
13 4
10 7
8 7
13 12
7 9
9 9
6 8
9 3
5 6
7 2
14 1
12 5
11 2
8 6
11 7
9 2
6 10
12 10
5 9
5 5
2 1
13 1
3 1
11 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 100 numbers