結果

問題 No.2597 Yet Another Topological Problem
ユーザー suisen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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';
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0