結果
問題 | No.2597 Yet Another Topological Problem |
ユーザー |
|
提出日時 | 2023-11-21 23:49:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,916 bytes |
コンパイル時間 | 911 ms |
コンパイル使用メモリ | 75,536 KB |
最終ジャッジ日時 | 2025-02-17 22:48:41 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 WA * 40 |
ソースコード
#include <iostream>#include <vector>const std::string Possible{"Possible"};const std::string Impossible{"Impossible"};/*** i(kp-1)* : i(kp+1)* : :* +-------+ ......i* | ..... |* | : : |* | : : |* | : : |* | : : |* | : : +---- ......-R+i* ---------+ : :.......* ...........:*/int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int p, q;std::cin >> p >> q;if (p == 1) {std::cout << Impossible << '\n';return 0;}std::cout << Possible << '\n';const int R = q / p;// k が満たすべき条件: (R-1)(kp+1) <= R(kp-1)// k=ceil(2R/(p+1)) で十分const int k = (2 * R + p) / (p + 1);std::vector<std::pair<int, int>> points;for (int i = 0; i < R; ++i) {int x = i * (k * p + 1);int y = i;// Rwhile (y > -R + i) {points.emplace_back(x, y);--y;}while (x < (i + 1) * (k * p - 1)) {points.emplace_back(x, y);++x;}// R + 1while (y < i + 1) {points.emplace_back(x, y);++y;}while (x < (i + 1) * (k * p + 1)) {points.emplace_back(x, y);++x;}}int x = R * (k * p + 1);int y = R;// Rwhile (y > 0) {points.emplace_back(x, y);--y;}while (x <= k * q) {points.emplace_back(x, y);++x;}// x 方向の長さの和 = kq <= 83500 where R<=250,2<=p<q<=500// y 方向の長さの和 = R(2R+2) <= 125500 where R<=250// 長さの和 <= 209000std::cout << points.size() << '\n';for (const auto &[x, y] : points) {std::cout << x << ' ' << y << '\n';}}