結果
問題 | 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; // R while (y > -R + i) { points.emplace_back(x, y); --y; } while (x < (i + 1) * (k * p - 1)) { points.emplace_back(x, y); ++x; } // R + 1 while (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; // R while (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 // 長さの和 <= 209000 std::cout << points.size() << '\n'; for (const auto &[x, y] : points) { std::cout << x << ' ' << y << '\n'; } }