QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#229661#7637. Exactly Three Neighborsucup-team055#AC ✓0ms3844kbC++233.1kb2023-10-28 16:38:062023-10-28 16:38:07

Judging History

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

  • [2023-10-28 16:38:07]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3844kb
  • [2023-10-28 16:38:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define all(a) begin(a), end(a)
template<class T> bool chmin(T& a, T b) { if(a <= b) return 0; a = b; return 1; }
template<class T> bool chmax(T& a, T b) { if(a >= b) return 0; a = b; return 1; }
ll dx[] = {0, 1, 0, -1};
ll dy[] = {1, 0, -1, 0};

#define EQ(a,b,op,c,d) ((a)*(d)op(c)*(b))
int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll p, q;
    cin >> p >> q;
    auto answer = [&](vector<string> S) {
        const ll H = S.size(), W = S[0].size();
        assert(H <= 1000);
        assert(W <= 1000);
        ll cnt = 0;
        for(auto& s : S) cnt += ranges::count(s, '#');
        assert(EQ(p,q,==,cnt,H*W));
        rep(i, 0, H) rep(j, 0, W) if(S[i][j] == '#') {
            ll cnt = 0;
            rep(d, 0, 4) {
                const ll x = (i + H + dx[d]) % H;
                const ll y = (j + W + dy[d]) % W;
                cnt += S[x][y] == '#';
            }
            assert(cnt == 3);
        }
        cout << H << ' ' << W << endl;
        for(auto& s : S) cout << s << '\n';
        exit(0);
    };
    if(p == 0) answer({"."});
    if(EQ(p,q,<=,2,3)) {
        ll a = 1, b = 2;
        while(EQ(p,q,<,2,b+2)){
            a++; b++;
        }
        for(ll xy=1; ; xy++) rep(x, 0, xy + 1) {
            const ll y = xy - x;
            if(EQ(2*(x+y),(a+2)*x+(b+2)*y,==,p,q)){
                string ans;
                rep(_, 0, x) ans += '#' + string(a, '.') + '#';
                rep(_, 0, y) ans += '#' + string(b, '.') + '#';
                answer({ans});
            }
        }
    }
    if(EQ(q-p,q,<,1,5)) {
        puts("-1 -1");
        return 0;
    }
    ll a = 1, b = 2;
    while(EQ(q-p,q,>,b,3*b+2)){
        a++; b++;
    }
    for(ll xy=1; ; xy++) rep(x, 0, xy + 1) {
        const ll y = xy - x;
        if(EQ(a*x+b*y,(3*a+2)*x+(3*b+2)*y,==,(q-p),q)){
            const ll h1 = (a+1) * x + (b+1) * y, w1 = x+y;
            const ll h2 = 1, w2 = 3;
            const ll W = w1 * w2, H = abs(h1 * (W / w1) - h2 * (W / w2));
            vector ans(H, string(H, '#'));
            vector<tuple<ll, ll, ll>> piece;
            {
                ll X = 0, Y = 0;
                rep(_, 0, H) {
                    rep(_, 0, x) {
                        piece.emplace_back(X, Y, a);
                        X += a + 1;
                        Y += 1;
                    }
                    rep(_, 0, y) {
                        piece.emplace_back(X, Y, b);
                        X += b + 1;
                        Y += 1;
                    }
                }
            }
            ll X = 0, Y = 0;
            auto at = [&](ll i, ll j) -> char& {
                return ans[i % H][j % H];
            };
            do {
                for(auto [dx, dy, a] : piece) {
                    rep(i, 0, a) at(X + dx + i, Y + dy) = '.';
                }
                X += 1;
                Y += 3;
            } while(Y % H);
            answer(ans);
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3

output:

1 3
#.#

result:

ok good solution

Test #2:

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

input:

1 1

output:

-1 -1

result:

ok no solution

Test #3:

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

input:

3 4

output:

8 8
.####.##
.##.####
###.##.#
#.####.#
#.##.###
####.##.
##.####.
##.##.##

result:

ok good solution

Test #4:

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

input:

3 5

output:

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

result:

ok good solution

Test #5:

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

input:

4 5

output:

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

result:

ok good solution

Test #6:

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

input:

7 10

output:

20 20
.####.##.##.##.##.##
.##.####.##.##.##.##
.##.##.####.##.##.##
.##.##.##.####.##.##
.##.##.##.##.####.##
.##.##.##.##.##.####
###.##.##.##.##.##.#
#.####.##.##.##.##.#
#.##.####.##.##.##.#
#.##.##.####.##.##.#
#.##.##.##.####.##.#
#.##.##.##.##.####.#
#.##.##.##.##.##.###
####.##.##.##.##.##.
...

result:

ok good solution

Test #7:

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

input:

5 7

output:

14 14
.####.##.##.##
.##.####.##.##
.##.##.####.##
.##.##.##.####
###.##.##.##.#
#.####.##.##.#
#.##.####.##.#
#.##.##.####.#
#.##.##.##.###
####.##.##.##.
##.####.##.##.
##.##.####.##.
##.##.##.####.
##.##.##.##.##

result:

ok good solution

Test #8:

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

input:

7 9

output:

18 18
.####.##.####.####
###.####.##.####.#
#.####.####.##.###
####.####.####.##.
##.####.####.####.
##.##.####.####.##
.####.##.####.####
###.####.##.####.#
#.####.####.##.###
####.####.####.##.
##.####.####.####.
##.##.####.####.##
.####.##.####.####
###.####.##.####.#
#.####.####.##.###
####.####...

result:

ok good solution

Test #9:

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

input:

0 1

output:

1 1
.

result:

ok good solution

Test #10:

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

input:

1 2

output:

1 4
#..#

result:

ok good solution

Test #11:

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

input:

1 3

output:

1 6
#....#

result:

ok good solution

Test #12:

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

input:

1 4

output:

1 8
#......#

result:

ok good solution

Test #13:

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

input:

1 5

output:

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

result:

ok good solution

Test #14:

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

input:

1 6

output:

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

result:

ok good solution

Test #15:

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

input:

1 7

output:

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

result:

ok good solution

Test #16:

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

input:

1 8

output:

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

result:

ok good solution

Test #17:

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

input:

1 9

output:

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

result:

ok good solution

Test #18:

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

input:

1 10

output:

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

result:

ok good solution

Test #19:

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

input:

2 5

output:

1 5
#...#

result:

ok good solution

Test #20:

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

input:

2 7

output:

1 7
#.....#

result:

ok good solution

Test #21:

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

input:

2 9

output:

1 9
#.......#

result:

ok good solution

Test #22:

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

input:

3 7

output:

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

result:

ok good solution

Test #23:

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

input:

3 8

output:

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

result:

ok good solution

Test #24:

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

input:

3 10

output:

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

result:

ok good solution

Test #25:

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

input:

4 7

output:

1 7
#.##..#

result:

ok good solution

Test #26:

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

input:

4 9

output:

1 9
#..##...#

result:

ok good solution

Test #27:

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

input:

5 6

output:

-1 -1

result:

ok no solution

Test #28:

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

input:

5 8

output:

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

result:

ok good solution

Test #29:

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

input:

5 9

output:

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

result:

ok good solution

Test #30:

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

input:

6 7

output:

-1 -1

result:

ok no solution

Test #31:

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

input:

7 8

output:

-1 -1

result:

ok no solution

Test #32:

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

input:

8 9

output:

-1 -1

result:

ok no solution

Test #33:

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

input:

9 10

output:

-1 -1

result:

ok no solution

Extra Test:

score: 0
Extra Test Passed