QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#229661 | #7637. Exactly Three Neighbors | ucup-team055# | AC ✓ | 0ms | 3844kb | C++23 | 3.1kb | 2023-10-28 16:38:06 | 2023-10-28 16:38:07 |
Judging History
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