QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#251689#7637. Exactly Three NeighborsikefumyAC ✓121ms3828kbC++203.8kb2023-11-14 23:25:322023-11-14 23:25:33

Judging History

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

  • [2023-11-14 23:25:33]
  • 评测
  • 测评结果:AC
  • 用时:121ms
  • 内存:3828kb
  • [2023-11-14 23:25:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define int128 __int128_t
#define pii128 pair<int128,int128>
const int inf = 1 << 30;
const ll linf = 1e18;
const ll mod = 1e9 + 7;
const db EPS = 1e-10;
const db pi = acos(-1);
template<class T> bool chmin(T& x, T y){
    if(x > y) {
        x = y;
        return true;
    } else return false;
}
template<class T> bool chmax(T& x, T y){
    if(x < y) {
        x = y;
        return true;
    } else return false;
}

// overload macro
#define CAT( A, B ) A ## B
#define SELECT( NAME, NUM ) CAT( NAME, NUM )

#define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT
#define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 )

#define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__)

// rep(overload)
#define rep( ... ) VA_SELECT(rep, __VA_ARGS__)
#define rep2(i, n) for (int i = 0; i < int(n); i++)
#define rep3(i, a, b) for (int i = a; i < int(b); i++)
#define rep4(i, a, b, c) for (int i = a; i < int(b); i += c)

// repll(overload)
#define repll( ... ) VA_SELECT(repll, __VA_ARGS__)
#define repll2(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repll3(i, a, b) for (ll i = a; i < (ll)(b); i++)
#define repll4(i, a, b, c) for (ll i = a; i < (ll)(b); i += c)

// rrep(overload)
#define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__)    
#define rrep2(i, n) for (int i = n - 1; i >= 0; i--)
#define rrep3(i, a, b) for (int i = b - 1; i >= a; i--)
#define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c)

// rrepll(overload)
#define rrepll( ... ) VA_SELECT(rrepll, __VA_ARGS__)
#define rrepll2(i, n) for (ll i = (ll)(n) - 1; i >= 0ll; i--)
#define rrepll3(i, a, b) for (ll i = b - 1; i >= (ll)(a); i--)
#define rrepll4(i, a, b, c) for (ll i = b - 1; i >= (ll)(a); i -= c)

// for_earh
#define fore(e, v) for (auto&& e : v)

// vector
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

int h, w;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int p, q;
    cin >> p >> q;
    // p = 7 , q = 9;
    int g = gcd(p, q);
    p /= g, q /= g;

    if (p * 5 > q * 4) {
        cout << "-1 -1\n";
        return 0;
    }

    if (p <= 2) h = 2 * q, w = 1;
    else if (p == 7 && q == 9) h = 18, w = 6;
    else if (p == 4 && q == 5) h = 10, w = 10;
    else h = 2 * q, w = 4;
    int d = (h * w) / q * (q - p);
    vector<string> S(h, string(w, '#'));

    auto judge = [&](int i, int j) -> bool {
        if (S[i][j] == '.') return true;
        int cnt = 0;
        rep (k, 4) {
            int rx = (i + dx[k] + h) % h;
            int ry = (j + dy[k] + w) % w;
            cnt += S[rx][ry] == '#';
        }
        return cnt == 3;
    };

    auto dfs = [&](auto&& self, int cnt, int idx) -> bool {
        if (cnt + (h * w) - idx < d || cnt > d) return false;
        if (idx == h * w) {
            bool ret = true;
            rep (i, 2) rep (j, w) {
                ret &= judge((h - i) % h, j);
            }
            return ret;
        }

        int x = idx / w, y = idx % w;

        if (x <= 1 || judge(x - 1, y)) {
            if (self(self, cnt, idx + 1)) return true;
        }

        S[x][y] = '.';
        if (x <= 1 || judge(x - 1, y)) {
            if (self(self, cnt + 1, idx + 1)) return true;
        }

        S[x][y] = '#';

        return false;
    };

    auto flag = dfs(dfs, 0, 0);
    if (flag) {
        cout << h << ' ' << w << endl;
        rep (i, h) cout << S[i] << endl;
    } else {
        cout << "NO" << endl;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3

output:

6 1
#
#
.
#
#
.

result:

ok good solution

Test #2:

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

input:

1 1

output:

-1 -1

result:

ok no solution

Test #3:

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

input:

3 4

output:

8 4
####
##..
####
..##
####
##..
####
..##

result:

ok good solution

Test #4:

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

input:

3 5

output:

10 4
####
####
....
####
####
....
####
####
....
....

result:

ok good solution

Test #5:

score: 0
Accepted
time: 121ms
memory: 3532kb

input:

4 5

output:

10 10
####.####.
##.####.##
.####.####
###.####.#
#.####.###
####.####.
##.####.##
.####.####
###.####.#
#.####.###

result:

ok good solution

Test #6:

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

input:

7 10

output:

20 4
####
##..
####
..##
####
##..
####
..##
####
##..
####
..##
####
##..
####
..##
..##
..##
..##
..##

result:

ok good solution

Test #7:

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

input:

5 7

output:

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

result:

ok good solution

Test #8:

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

input:

7 9

output:

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

result:

ok good solution

Test #9:

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

input:

0 1

output:

2 1
.
.

result:

ok good solution

Test #10:

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

input:

1 2

output:

4 1
#
#
.
.

result:

ok good solution

Test #11:

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

input:

1 3

output:

6 1
#
#
.
.
.
.

result:

ok good solution

Test #12:

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

input:

1 4

output:

8 1
#
#
.
.
.
.
.
.

result:

ok good solution

Test #13:

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

input:

1 5

output:

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

result:

ok good solution

Test #14:

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

input:

1 6

output:

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

result:

ok good solution

Test #15:

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

input:

1 7

output:

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

result:

ok good solution

Test #16:

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

input:

1 8

output:

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

result:

ok good solution

Test #17:

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

input:

1 9

output:

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

result:

ok good solution

Test #18:

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

input:

1 10

output:

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

result:

ok good solution

Test #19:

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

input:

2 5

output:

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

result:

ok good solution

Test #20:

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

input:

2 7

output:

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

result:

ok good solution

Test #21:

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

input:

2 9

output:

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

result:

ok good solution

Test #22:

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

input:

3 7

output:

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

result:

ok good solution

Test #23:

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

input:

3 8

output:

16 4
####
####
....
####
####
....
####
####
....
....
....
....
....
....
....
....

result:

ok good solution

Test #24:

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

input:

3 10

output:

20 4
####
####
....
####
####
....
####
####
....
....
....
....
....
....
....
....
....
....
....
....

result:

ok good solution

Test #25:

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

input:

4 7

output:

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

result:

ok good solution

Test #26:

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

input:

4 9

output:

18 4
####
####
....
####
####
....
####
####
....
####
####
....
....
....
....
....
....
....

result:

ok good solution

Test #27:

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

input:

5 6

output:

-1 -1

result:

ok no solution

Test #28:

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

input:

5 8

output:

16 4
####
####
....
####
####
....
####
####
....
####
####
....
####
####
....
....

result:

ok good solution

Test #29:

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

input:

5 9

output:

18 4
####
####
....
####
####
....
####
####
....
####
####
....
####
####
....
....
....
....

result:

ok good solution

Test #30:

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

input:

6 7

output:

-1 -1

result:

ok no solution

Test #31:

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

input:

7 8

output:

-1 -1

result:

ok no solution

Test #32:

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

input:

8 9

output:

-1 -1

result:

ok no solution

Test #33:

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

input:

9 10

output:

-1 -1

result:

ok no solution

Extra Test:

score: 0
Extra Test Passed