QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#506739#7637. Exactly Three Neighborspandapythoner#AC ✓297ms3876kbC++232.9kb2024-08-05 21:03:032024-08-05 21:03:04

Judging History

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

  • [2024-08-05 21:03:04]
  • 评测
  • 测评结果:AC
  • 用时:297ms
  • 内存:3876kb
  • [2024-08-05 21:03:03]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;


using ll = long long;

#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
#define len(a) ((int)(a).size())


const ll inf = 1e18;
mt19937 rnd(234);


vector<string> anses[11][11];
const int maxn = 6;
const int maxm = 18;
int cur[maxn][maxm];


int get(int i, int j, int n, int m) {
    if (i < 0) i += n;
    if (j < 0) j += m;
    if (i >= n) i -= n;
    if (j >= m) j -= m;
    return cur[i][j];
}


bool check(int i, int j, int n, int m) {
    if (!get(i, j, n, m)) return true;
    return get(i - 1, j, n, m) + get(i + 1, j, n, m) + get(i, j - 1, n, m) + get(i, j + 1, n, m) == 3;
}


void rec(int i, int j, int n, int cnt) {
    if (i == 0 and j > 0) {
        int m = j;
        bool ok = true;
        rep(k, n)
            if (!check(k, m - 1, n, m) or !check(k, 0, n, m)) {
                ok = false;
                break;
            }
        if (ok) {
            int p = cnt;
            int q = n * m;
            int g = gcd(p, q);
            p /= g;
            q /= g;
            if (p <= 10 and q <= 10 and anses[p][q].empty()) {
                anses[p][q] = {};
                rep(i, n) {
                    string s;
                    s.resize(m);
                    rep(j, m) s[j] = (cur[i][j] ? '#' : '.');
                    anses[p][q].push_back(s);
                }
            }
        }
    }
    if (j == maxm) {
        return;
    }
    rep(val, 2) {
        cur[i][j] = val;
        if (j > 1 and !check(i, j - 1, n, maxm)) continue;
        int ni = i + 1;
        int nj = j;
        if (ni == n) {
            ni = 0;
            nj += 1;
        }
        rec(ni, nj, n, cnt + val);
    }
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    rep(p, 11) rep(q, 11) anses[p][q] = vector<string>();
    for (int n = 1; n <= maxn; n += 1) {
        rec(0, 0, n, 0);
    }
    int p, q;
    cin >> p >> q;
    if (anses[p][q].empty()) {
        if (3 * p <= 2 * q) {
            int b = 2 * p;
            int w = 2 * (q - p);
            vector<int> buckets(b / 2);
            int i = 0;
            rep(cnt, w) {
                buckets[i] += 1;
                i = (i + 1) % (b / 2);
            }
            cout << 1 << " " << b + w << "\n";
            rep(i, b / 2) {
                cout << "##";
                assert(buckets[i] > 0);
                rep(k, buckets[i]) cout << ".";
            }
            cout << "\n";
            return 0;
        }
        cout << -1 << " " << -1 << "\n";
        return 0;
    }
    int n = len(anses[p][q]);
    int m = len(anses[p][q][0]);
    cout << n << " " << m << "\n";
    rep(i, n) {
        cout << anses[p][q][i] << "\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 292ms
memory: 3584kb

input:

2 3

output:

1 3
.##

result:

ok good solution

Test #2:

score: 0
Accepted
time: 290ms
memory: 3676kb

input:

1 1

output:

-1 -1

result:

ok no solution

Test #3:

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

input:

3 4

output:

4 4
.###
.###
##.#
##.#

result:

ok good solution

Test #4:

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

input:

3 5

output:

1 10
..##.##.##

result:

ok good solution

Test #5:

score: 0
Accepted
time: 293ms
memory: 3588kb

input:

4 5

output:

5 5
.####
###.#
#.###
####.
##.##

result:

ok good solution

Test #6:

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

input:

7 10

output:

4 15
....###.###.###
....###.###.###
#####.###.###.#
#####.###.###.#

result:

ok good solution

Test #7:

score: 0
Accepted
time: 293ms
memory: 3612kb

input:

5 7

output:

4 14
...###.###.###
...###.###.###
####.###.###.#
####.###.###.#

result:

ok good solution

Test #8:

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

input:

7 9

output:

6 18
.####.####.####.##
.##.####.####.####
###.##.####.####.#
#.####.##.####.###
####.####.##.####.
##.####.####.##.##

result:

ok good solution

Test #9:

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

input:

0 1

output:

1 1
.

result:

ok good solution

Test #10:

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

input:

1 2

output:

1 16
.....##.##.##.##

result:

ok good solution

Test #11:

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

input:

1 3

output:

1 18
..........##.##.##

result:

ok good solution

Test #12:

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

input:

1 4

output:

1 16
...........##.##

result:

ok good solution

Test #13:

score: 0
Accepted
time: 290ms
memory: 3836kb

input:

1 5

output:

1 10
........##

result:

ok good solution

Test #14:

score: 0
Accepted
time: 291ms
memory: 3868kb

input:

1 6

output:

1 12
..........##

result:

ok good solution

Test #15:

score: 0
Accepted
time: 292ms
memory: 3876kb

input:

1 7

output:

1 14
............##

result:

ok good solution

Test #16:

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

input:

1 8

output:

1 16
..............##

result:

ok good solution

Test #17:

score: 0
Accepted
time: 288ms
memory: 3836kb

input:

1 9

output:

1 18
................##

result:

ok good solution

Test #18:

score: 0
Accepted
time: 290ms
memory: 3652kb

input:

1 10

output:

1 20
##..................

result:

ok good solution

Test #19:

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

input:

2 5

output:

1 15
.......##.##.##

result:

ok good solution

Test #20:

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

input:

2 7

output:

1 14
.........##.##

result:

ok good solution

Test #21:

score: 0
Accepted
time: 291ms
memory: 3588kb

input:

2 9

output:

1 18
.............##.##

result:

ok good solution

Test #22:

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

input:

3 7

output:

1 14
......##.##.##

result:

ok good solution

Test #23:

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

input:

3 8

output:

1 16
........##.##.##

result:

ok good solution

Test #24:

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

input:

3 10

output:

1 20
##.....##.....##....

result:

ok good solution

Test #25:

score: 0
Accepted
time: 290ms
memory: 3524kb

input:

4 7

output:

1 14
...##.##.##.##

result:

ok good solution

Test #26:

score: 0
Accepted
time: 291ms
memory: 3520kb

input:

4 9

output:

1 18
.......##.##.##.##

result:

ok good solution

Test #27:

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

input:

5 6

output:

-1 -1

result:

ok no solution

Test #28:

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

input:

5 8

output:

1 16
..##.##.##.##.##

result:

ok good solution

Test #29:

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

input:

5 9

output:

1 18
....##.##.##.##.##

result:

ok good solution

Test #30:

score: 0
Accepted
time: 291ms
memory: 3524kb

input:

6 7

output:

-1 -1

result:

ok no solution

Test #31:

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

input:

7 8

output:

-1 -1

result:

ok no solution

Test #32:

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

input:

8 9

output:

-1 -1

result:

ok no solution

Test #33:

score: 0
Accepted
time: 296ms
memory: 3520kb

input:

9 10

output:

-1 -1

result:

ok no solution

Extra Test:

score: 0
Extra Test Passed