結果
問題 | No.2597 Yet Another Topological Problem |
ユーザー |
|
提出日時 | 2023-11-22 00:09:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,914 bytes |
コンパイル時間 | 702 ms |
コンパイル使用メモリ | 74,472 KB |
最終ジャッジ日時 | 2025-02-17 22:49:22 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 WA * 15 |
ソースコード
#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(kp+1)-R(kp-1) < kp// k=ceil(2R/p) で十分const int k = (2 * R + p - 1) / p;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 <= 124500 where R<=249,2<=p<q<=500// y 方向の長さの和 = R(2R+2) <= 124500 where R<=249// 長さの和 <= 249000std::cout << points.size() - 1 << '\n';for (const auto &[x, y] : points) {std::cout << x << ' ' << y << '\n';}}