QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#265431#7740. Puzzle: Question Markucup-team1198AC ✓232ms20628kbC++208.3kb2023-11-25 18:23:452023-11-25 18:23:45

Judging History

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

  • [2023-11-25 18:23:45]
  • 评测
  • 测评结果：AC
  • 用时：232ms
  • 内存：20628kb
查看
  • [2023-11-25 18:23:45]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

const int MAXN = 2e3 + 100;
int a[MAXN][MAXN];

int id;

void col24(int i, int j) {
    a[i][j] = a[i + 1][j] = a[i][j + 1] = a[i + 1][j + 2] = id;
    ++id;
    a[i + 1][j + 1] = a[i][j + 2] = a[i][j + 3] = a[i + 1][j + 3] = id;
    ++id;
}

void col42(int i, int j) {
    a[i][j] = a[i][j + 1] = a[i + 1][j] = a[i + 2][j + 1] = id;
    ++id;
    a[i + 1][j + 1] = a[i + 2][j] = a[i + 3][j] = a[i + 3][j + 1] = id;
    ++id;
}

void col33(int i, int j) {
    a[i][j] = a[i + 1][j + 1] = a[i + 2][j] = a[i + 2][j + 1] = id;
    ++id;
    a[i + 1][j] = a[i][j + 1] = a[i][j + 2] = a[i + 1][j + 2] = id;
    ++id;
}

void coli33(int i, int j) {
    a[i + 1][j] = a[i + 2][j] = a[i + 1][j + 1] = a[i + 2][j + 2] = id;
    ++id;
    a[i][j + 1] = a[i][j + 2] = a[i + 1][j + 2] = a[i + 2][j + 1] = id;
    ++id;
}

void collll33(int i, int j) {
    a[i][j] = a[i + 1][j] = a[i][j + 1] = a[i + 2][j + 1] = id;
    ++id;
    a[i + 2][j] = a[i + 1][j + 1] = a[i + 1][j + 2] = a[i + 2][j + 2] = id;
    ++id;
}

void colrrr33(int i, int j) {
    a[i][j] = a[i][j + 1] = a[i + 1][j] = a[i + 1][j + 2] = id;
    ++id;
    a[i][j + 2] = a[i + 1][j + 1] = a[i + 2][j + 1] = a[i + 2][j + 2] = id;
    ++id;
}

void colw1(int i, int j) {
    a[i][j] = a[i][j + 1] = a[i + 1][j] = a[i + 2][j + 1] = id;
    ++id;
    a[i + 1][j + 1] = a[i + 1][j + 2] = a[i + 2][j + 2] = a[i + 3][j + 1] = id;
    ++id;
}

void colw2(int i, int j) {
    a[i][j] = a[i][j + 1] = a[i + 1][j] = a[i + 2][j + 1] = id;
    ++id;
    a[i + 1][j + 1] = a[i + 2][j + 2] = a[i + 3][j + 2] = a[i + 3][j + 1] = id;
    ++id;
}

int sn;

void print() {
    cout << id - 1 << "\n";
    for (int i = 0; i < sn; ++i) {
        /// cout << "{";
        for (int j = 0; j < sn; ++j) {
            cout << a[i][j];
            if (j != sn - 1) {
                cout << " ";
            }
        }
        /// cout << "},";
        cout << "\n";
    }
}

vector<vector<array<int, 2>>> go = {
    {{0, 0}, {1, 1}, {1, 2}, {0, 2}},
    {{0, 0}, {1, 1}, {2, 1}, {2, 0}}
};

void solve(int k) {
    if (k * 4 + 1 == sn * sn) {
        print();
        exit(0);
    }
    int ipos = -1;
    int jpos = -1;
    for (int i = 0; i < sn; ++i) {
        for (int j = 0; j < sn; ++j) {
            if (a[i][j] == 0) {
                ipos = i;
                jpos = j;
            }
        }
    }
    for (int i = 0; i < sn; ++i) {
        for (int j = 0; j < sn; ++j) {
            for (int mask = 0; mask < 4; ++mask) {
                for (auto form : go) {
                    vector<array<int, 2>> pos;
                    for (auto d : form) {
                        int i1 = i;
                        int j1 = j;
                        if (mask & 1) {
                            i1 += d[0];
                        } else {
                            i1 -= d[0];
                        }
                        if (mask & 2) {
                            j1 += d[1];
                        } else {
                            j1 -= d[1];
                        }
                        if (i1 >= 0 && i1 < sn && j1 >= 0 && j1 < sn && a[i1][j1] == 0) {
                            pos.push_back({i1, j1});
                        }
                    }
                    if ((int)pos.size() != 4) continue;
                    bool f = false;
                    for (auto elem : pos) {
                        if (elem[0] == ipos && elem[1] == jpos) {
                            f = true;
                            break;
                        }
                    }
                    if (!f) continue;
                    for (auto elem : pos) {
                        a[elem[0]][elem[1]] = k + 1;
                    }
                    solve(k + 1);
                    for (auto elem : pos) {
                        a[elem[0]][elem[1]] = 0;
                    }
                }
            }
        }
    }
}

vector<vector<int>> magic13 = {
    {40, 42, 42, 39, 39, 41, 38, 41, 37, 37, 0, 36, 36},
    {42, 40, 42, 35, 39, 41, 41, 38, 37, 34, 34, 33, 36},
    {40, 40, 35, 39, 32, 32, 38, 38, 31, 37, 34, 36, 33},
    {29, 29, 35, 35, 32, 27, 27, 31, 30, 34, 30, 33, 33},
    {28, 29, 28, 25, 25, 32, 27, 31, 31, 30, 30, 26, 26},
    {29, 28, 28, 22, 25, 27, 21, 24, 24, 23, 26, 23, 26},
    {20, 20, 22, 25, 19, 19, 24, 21, 24, 23, 23, 18, 18},
    {16, 20, 22, 22, 19, 14, 21, 21, 13, 13, 17, 17, 18},
    {20, 16, 12, 15, 15, 19, 14, 11, 11, 13, 17, 18, 17},
    {16, 16, 15, 12, 15, 14, 14, 11, 13, 9, 9, 8, 8},
    {7, 7, 12, 12, 5, 10, 10, 3, 11, 2, 9, 1, 8},
    {6, 7, 6, 5, 4, 10, 4, 10, 3, 9, 2, 8, 1},
    {7, 6, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1}
};

void solve() {
    int n;
    cin >> n;
    sn = n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            a[i][j] = 0;
        }
    }
    id = 1;
    if (n % 4 == 0) {
        for (int i = 0; i < n; i += 2) {
            for (int j = 0; j < n; j += 4) {
                col24(i, j);
            }
        }
        print();
        return;
    }
    if (n % 4 == 2) {
        for (int i = 0; i < n; i += 2) {
            for (int j = 0; j < n - 2; j += 4) {
                col24(i, j);
            }
        }
        for (int i = 0; i < n - 2; i += 4) {
            col42(i, n - 2);
        }
        print();
        return;
    }
    if (n == 5 || n == 7 || n == 1) {
        if (n % 4 == 3) {
            for (int i = 0; i < n - 3; i += 4) {
                col24(n - 2, i);
                col42(i, n - 2);
            }
            coli33(n - 3, n - 3);
            n -= 2;
        }
        if (n < 4) {
            print();
            return;
        }
        int l = 0;
        int r = n;
        while (r - l > 5) {
            col33(l, l);
            for (int i = l + 3; i + 4 <= r; i += 4) {
                col24(l, i);
                col42(i, l);
            }
            for (int i = l; i + 4 <= r; i += 4) {
                col24(r - 2, i);
                if (i != r - 5) {
                    col42(i, r - 2);
                }
            }
            coli33(r - 5, r - 3);
            l += 2;
            r -= 2;
        }
        col33(l, l);
        col24(l + 3, l);
        a[l + 2][l + 2] = a[l + 1][l + 3] = a[l + 1][l + 4] = a[l + 2][l + 4] = id;
        ++id;
        print();
        return;
    }
    int lx = 0, rx = n, ly = 0, ry = n;
    while (rx - lx > 3) {
        int n = rx - lx;
        if (n == 13) {
            for (int i = 0; i < 13; ++i) {
                for (int j = 0; j < 13; ++j) {
                    if (magic13[i][j] != 0) {
                        a[i + lx][j + ly] = magic13[i][j] + id - 1;
                    }
                }
            }
            id += (168 / 4);
            print();
            return;
        }
        if ((rx - lx) % 4 == 3) {
            for (int i = 0; i < n - 3; i += 4) {
                col24(lx + n - 2, ly + i);
                col42(lx + i, ly + n - 2);
            }
            coli33(lx + n - 3, ly + n - 3);
            rx -= 2;
            ry -= 2;
            continue;
        }
        col42(lx, ly);
        col33(lx, ly + 2);
        for (int i = ly + 5; i + 4 <= ry; i += 4) {
            col24(lx, i);
        }
        for (int i = lx + 7; i + 2 <= rx; i += 2) {
            col24(i, ly);
        }
        for (int i = lx + 5; i + 4 <= rx; i += 4) {
            col42(i, ry - 2);
        }
        collll33(lx + 4, ly);
        colrrr33(lx + 2, ry - 3);
        colw1(lx + 3, ly + 2);
        for (int i = ly + 4; i <= ry - 5; i += 2) {
            colw2(lx + 2, i);
        }
        lx += 6;
        ly += 4;
        ry -= 2;
        continue;
    }
    col33(lx, ly);
    print();
}

/**
40 42 42 39 39 41 38 41 37 37  0 36 36
42 40 42 35 39 41 41 38 37 34 34 33 36
40 40 35 39 32 32 38 38 31 37 34 36 33
29 29 35 35 32 27 27 31 30 34 30 33 33
28 29 28 25 25 32 27 31 31 30 30 26 26
29 28 28 22 25 27 21 24 24 23 26 23 26
20 20 22 25 19 19 24 21 24 23 23 18 18
16 20 22 22 19 14 21 21 13 13 17 17 18
20 16 12 15 15 19 14 11 11 13 17 18 17
16 16 15 12 15 14 14 11 13  9  9  8  8
 7  7 12 12  5 10 10  3 11  2  9  1  8
 6  7  6  5  4 10  4 10  3  9  2  8  1
 7  6  6  5  5  4  4  3  3  2  2  1  1
 */

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }

    return 0;
}
Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

2
3
4

output:

2
1 2 2
2 1 2
1 1 0
4
1 1 2 2
1 2 1 2
3 3 4 4
3 4 3 4

result:

ok Correct. (2 test cases)

Test #2:

score: 0
Accepted
time: 203ms
memory: 6676kb

input:

246
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
...

output:

0
0
0
0 0
0 0
2
1 2 2
2 1 2
1 1 0
4
1 1 2 2
1 2 1 2
3 3 4 4
3 4 3 4
5
1 2 2 0 0
2 1 2 5 5
1 1 5 0 5
3 3 4 4 0
3 4 3 4 0
8
1 1 2 2 7 7
1 2 1 2 7 8
3 3 4 4 8 7
3 4 3 4 8 8
5 5 6 6 0 0
5 6 5 6 0 0
11
7 8 8 0 0 3 3
8 7 8 11 11 3 4
7 7 11 0 11 4 3
9 9 10 10 0 4 4
9 10 9 10 0 6 6
1 1 2 2 5 5 6
1 2 1 2 5 6...

result:

ok Correct. (246 test cases)

Test #3:

score: 0
Accepted
time: 198ms
memory: 6512kb

input:

64
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310

output:

15252
247 247 249 250 250 251 251 252 252 253 253 254 254 255 255 256 256 257 257 258 258 259 259 260 260 261 261 262 262 263 263 264 264 265 265 266 266 267 267 268 268 269 269 270 270 271 271 272 272 273 273 274 274 275 275 276 276 277 277 278 278 279 279 280 280 281 281 282 282 283 283 284 284 28...

result:

ok Correct. (64 test cases)

Test #4:

score: 0
Accepted
time: 195ms
memory: 6920kb

input:

45
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355

output:

24180
311 311 313 314 314 315 315 316 316 317 317 318 318 319 319 320 320 321 321 322 322 323 323 324 324 325 325 326 326 327 327 328 328 329 329 330 330 331 331 332 332 333 333 334 334 335 335 336 336 337 337 338 338 339 339 340 340 341 341 342 342 343 343 344 344 345 345 346 346 347 347 348 348 34...

result:

ok Correct. (45 test cases)

Test #5:

score: 0
Accepted
time: 191ms
memory: 7216kb

input:

35
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390

output:

31684
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...

result:

ok Correct. (35 test cases)

Test #6:

score: 0
Accepted
time: 202ms
memory: 7784kb

input:

30
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420

output:

38220
391 391 393 394 394 395 395 396 396 397 397 398 398 399 399 400 400 401 401 402 402 403 403 404 404 405 405 406 406 407 407 408 408 409 409 410 410 411 411 412 412 413 413 414 414 415 415 416 416 417 417 418 418 419 419 420 420 421 421 422 422 423 423 424 424 425 425 426 426 427 427 428 428 42...

result:

ok Correct. (30 test cases)

Test #7:

score: 0
Accepted
time: 217ms
memory: 20296kb

input:

2
2000
1000

output:

1000000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 5...

result:

ok Correct. (2 test cases)

Test #8:

score: 0
Accepted
time: 218ms
memory: 20388kb

input:

2
1999
999

output:

999000
1999 1999 2001 2002 2002 2003 2003 2004 2004 2005 2005 2006 2006 2007 2007 2008 2008 2009 2009 2010 2010 2011 2011 2012 2012 2013 2013 2014 2014 2015 2015 2016 2016 2017 2017 2018 2018 2019 2019 2020 2020 2021 2021 2022 2022 2023 2023 2024 2024 2025 2025 2026 2026 2027 2027 2028 2028 2029 202...

result:

ok Correct. (2 test cases)

Test #9:

score: 0
Accepted
time: 192ms
memory: 20452kb

input:

2
1998
998

output:

998000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

result:

ok Correct. (2 test cases)

Test #10:

score: 0
Accepted
time: 210ms
memory: 19960kb

input:

2
1997
997

output:

997002
1 1 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 53...

result:

ok Correct. (2 test cases)

Test #11:

score: 0
Accepted
time: 213ms
memory: 20008kb

input:

2
1996
996

output:

996004
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

result:

ok Correct. (2 test cases)

Test #12:

score: 0
Accepted
time: 226ms
memory: 20628kb

input:

2
1995
995

output:

995006
1995 1995 1997 1998 1998 1999 1999 2000 2000 2001 2001 2002 2002 2003 2003 2004 2004 2005 2005 2006 2006 2007 2007 2008 2008 2009 2009 2010 2010 2011 2011 2012 2012 2013 2013 2014 2014 2015 2015 2016 2016 2017 2017 2018 2018 2019 2019 2020 2020 2021 2021 2022 2022 2023 2023 2024 2024 2025 202...

result:

ok Correct. (2 test cases)

Test #13:

score: 0
Accepted
time: 208ms
memory: 20396kb

input:

2
1994
994

output:

994008
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

result:

ok Correct. (2 test cases)

Test #14:

score: 0
Accepted
time: 219ms
memory: 20328kb

input:

2
1993
993

output:

993012
1 1 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 53...

result:

ok Correct. (2 test cases)

Test #15:

score: 0
Accepted
time: 194ms
memory: 20220kb

input:

2
1992
992

output:

992016
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

result:

ok Correct. (2 test cases)

Test #16:

score: 0
Accepted
time: 232ms
memory: 20200kb

input:

2
1991
991

output:

991020
1991 1991 1993 1994 1994 1995 1995 1996 1996 1997 1997 1998 1998 1999 1999 2000 2000 2001 2001 2002 2002 2003 2003 2004 2004 2005 2005 2006 2006 2007 2007 2008 2008 2009 2009 2010 2010 2011 2011 2012 2012 2013 2013 2014 2014 2015 2015 2016 2016 2017 2017 2018 2018 2019 2019 2020 2020 2021 202...

result:

ok Correct. (2 test cases)

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-03 20:59:15 | OpenSource Project