QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#232003 | #7637. Exactly Three Neighbors | hos_lyric | AC ✓ | 1ms | 3760kb | C++14 | 4.1kb | 2023-10-29 18:53:53 | 2023-10-29 18:53:54 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
constexpr int DX[4] = {+1, 0, -1, 0};
constexpr int DY[4] = {0, +1, 0, -1};
vector<string> solve(int P, int Q) {
// P/Q <= 2/3
if (3 * P <= 2 * Q) {
string a(2 * Q, '.');
for (int i = 0; i < P; ++i) {
a[3 * i] = a[3 * i + 1] = '#';
}
return {a};
} else if (P == 3 && Q == 4) {
vector<string> a(4, string(4, '#'));
a[0][0] = a[0][1] = a[2][2] = a[2][3] = '.';
return a;
} else if (P == 4 && Q == 5) {
vector<string> a(5, string(5, '#'));
for (int x = 0; x < 5; ++x) {
a[x][(2 * x) % 5] = '.';
}
return a;
} else if (P == 5 && Q == 7) {
vector<string> a(14, string(4, '#'));
a[0][0] = a[0][1] = a[1][0] = a[1][1] = a[3][2] = a[3][3] = a[5][0] = a[5][1] = '.';
for (int x = 0; x < 7; ++x) for (int y = 0; y < 4; ++y) {
a[x + 7][(y + 2) % 4] = a[x][y];
}
return a;
} else if (P == 7 && Q == 9) {
vector<string> a(18, string(6, '#'));
for (int i = 0; i < 6; ++i) {
a[3 * i + 0][(i + 0) % 6] = '.';
a[3 * i + 0][(i + 1) % 6] = '.';
a[3 * i + 1][(i + 3) % 6] = '.';
a[3 * i + 2][(i + 5) % 6] = '.';
}
return a;
} else if (P == 7 && Q == 10) {
vector<string> a(5, string(4, '#'));
a[0][0] = a[0][1] = a[1][0] = a[1][1] = a[3][2] = a[3][3] = '.';
return a;
} else {
return {};
}
}
void judge(int P, int Q, const vector<string> &a) {
const int m = a.size(), n = a[0].size();
for (int x = 0; x < m; ++x) {
assert((int)a[x].size() == n);
for (int y = 0; y < n; ++y) {
assert(a[x][y] == '#' || a[x][y] == '.');
}
}
int cnt = 0;
for (int x = 0; x < m; ++x) for (int y = 0; y < n; ++y) if (a[x][y] == '#') {
++cnt;
int deg = 0;
for (int dir = 0; dir < 4; ++dir) {
const int xx = (x + DX[dir] + m) % m;
const int yy = (y + DY[dir] + n) % n;
if (a[xx][yy] == '#') {
++deg;
}
}
assert(deg == 3);
}
// P/Q = cnt/mn
assert(P * m * n == Q * cnt);
}
int main() {
#ifdef LOCAL
for (int Q = 0; Q <= 10; ++Q) for (int P = 0; P <= Q; ++P) if (__gcd(P, Q) == 1) {
cerr << COLOR("33") << P << "/" << Q << COLOR() << endl;
const auto ans = solve(P, Q);
if (!ans.empty()) {
for (const auto &row : ans) {
cerr << row << endl;
}
judge(P, Q, ans);
} else {
cerr << "no solution" << endl;
// P/Q <= 4/5
if (5 * P <= 4 * Q) {
cerr << COLOR("31") << "TODO" << COLOR() << endl;
}
}
}
#endif
int P, Q;
for (; ~scanf("%d%d", &P, &Q); ) {
const auto ans = solve(P, Q);
if (!ans.empty()) {
printf("%d %d\n", (int)ans.size(), (int)ans[0].size());
for (const auto &row : ans) {
puts(row.c_str());
}
} else {
puts("-1 -1");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3644kb
input:
2 3
output:
1 6 ##.##.
result:
ok good solution
Test #2:
score: 0
Accepted
time: 1ms
memory: 3432kb
input:
1 1
output:
-1 -1
result:
ok no solution
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 4
output:
4 4 ..## #### ##.. ####
result:
ok good solution
Test #4:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
3 5
output:
1 10 ##.##.##..
result:
ok good solution
Test #5:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
4 5
output:
5 5 .#### ##.## ####. #.### ###.#
result:
ok good solution
Test #6:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
7 10
output:
5 4 ..## ..## #### ##.. ####
result:
ok good solution
Test #7:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
5 7
output:
14 4 ..## ..## #### ##.. #### ..## #### ##.. ##.. #### ..## #### ##.. ####
result:
ok good solution
Test #8:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
7 9
output:
18 6 ..#### ###.## #####. #..### ####.# .##### ##..## #####. #.#### ###..# .##### ##.### ####.. #.#### ###.## .####. ##.### ####.#
result:
ok good solution
Test #9:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
0 1
output:
1 2 ..
result:
ok good solution
Test #10:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
1 2
output:
1 4 ##..
result:
ok good solution
Test #11:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
1 3
output:
1 6 ##....
result:
ok good solution
Test #12:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
1 4
output:
1 8 ##......
result:
ok good solution
Test #13:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
1 5
output:
1 10 ##........
result:
ok good solution
Test #14:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
1 6
output:
1 12 ##..........
result:
ok good solution
Test #15:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 7
output:
1 14 ##............
result:
ok good solution
Test #16:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
1 8
output:
1 16 ##..............
result:
ok good solution
Test #17:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
1 9
output:
1 18 ##................
result:
ok good solution
Test #18:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
1 10
output:
1 20 ##..................
result:
ok good solution
Test #19:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
2 5
output:
1 10 ##.##.....
result:
ok good solution
Test #20:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
2 7
output:
1 14 ##.##.........
result:
ok good solution
Test #21:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 9
output:
1 18 ##.##.............
result:
ok good solution
Test #22:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
3 7
output:
1 14 ##.##.##......
result:
ok good solution
Test #23:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 8
output:
1 16 ##.##.##........
result:
ok good solution
Test #24:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
3 10
output:
1 20 ##.##.##............
result:
ok good solution
Test #25:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
4 7
output:
1 14 ##.##.##.##...
result:
ok good solution
Test #26:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
4 9
output:
1 18 ##.##.##.##.......
result:
ok good solution
Test #27:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
5 6
output:
-1 -1
result:
ok no solution
Test #28:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
5 8
output:
1 16 ##.##.##.##.##..
result:
ok good solution
Test #29:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5 9
output:
1 18 ##.##.##.##.##....
result:
ok good solution
Test #30:
score: 0
Accepted
time: 0ms
memory: 3432kb
input:
6 7
output:
-1 -1
result:
ok no solution
Test #31:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
7 8
output:
-1 -1
result:
ok no solution
Test #32:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
8 9
output:
-1 -1
result:
ok no solution
Test #33:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
9 10
output:
-1 -1
result:
ok no solution
Extra Test:
score: 0
Extra Test Passed