結果
問題 | No.2597 Yet Another Topological Problem |
ユーザー |
|
提出日時 | 2023-11-22 16:40:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,689 bytes |
コンパイル時間 | 1,048 ms |
コンパイル使用メモリ | 85,104 KB |
最終ジャッジ日時 | 2025-02-17 23:02:02 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 WA * 15 |
ソースコード
// <WA> 曲線長が上限ギリギリ収まっていない#include <algorithm>#include <iostream>#include <vector>const std::string Possible{ "Possible" };const std::string Impossible{ "Impossible" };/*** D は q の倍数とする。k=D/q: 拡大率** R=floor(q/p) として、次のような山(実線)を i=0,1,...,R まで並べる** x=i(kp-1)* : x=i(kp+1) 山の内側の点線 (山 i-1 を kp だけ右にシフトしたもの): 通行禁止* : :* +-------+ y=i* | ..... |* | : : |* | : : |* | : : |* | : : |* | : : +----- y=-R+i* ---------+ : :.......* ...........:** [拡大率 k (=D/q) が満たすべき条件]* 1. R(kp+1)-R(kp-1) < kp : R番目の山の幅が kp 未満* 2. kq - R(kp-1) < kp : R番目の山の左端と kq(=D) の距離が kp 未満* 3. R(kp+1) <= kq : R番目の山の右端より右側 (inclusive) に kq(=D) が存在** それぞれ整理すると* 1. k >= ceil((2R+1)/p)* 2. k >= ceil((R+1)/(p(R+1)-q)* 3. k >= ceil(R/(q-pR))** つまり k は 1,2,3 の右辺の最大値を取れば十分** [線分の長さ]* - x 方向: kq* - y 方向: R((R+1)+R)+R = 2R(R+1)** R,k,q の最大値は?* - R: 249* - k: 250* - q: 500** 結局 kq + 2R(R+1) <= 249500 なので長さの制約は OK** [座標の大きさ]* - x 方向: 0<=x<=kq なので |x|<=125000 で OK* - y 方向: -R<=y<=R なので |y|<=500 で OK*/void debug(const std::vector<std::pair<int, int>>& points) {int maxx = 0;int miny = 0, maxy = 0;for (const auto& [x, y] : points) {maxx = std::max(maxx, x);miny = std::min(miny, y);maxy = std::max(maxy, y);}std::vector<std::string> lines_(maxy - miny + 1, std::string(maxx + 1, ' '));auto lines = lines_.rend() - (maxy + 1);for (int x = 0; x <= maxx; ++x) {lines[0][x] = '.';}lines[0][0] = '+';for (size_t i = 1; i < points.size(); ++i) {auto [px, py] = points[i - 1];auto [cx, cy] = points[i];if (i + 1 == points.size()) {lines[cy][cx] = '+';} else {auto [nx, ny] = points[i + 1];bool cv = px == cx;bool nv = cx == nx;if (cv != nv) {lines[cy][cx] = '+';} else if (cv) {lines[cy][cx] = '|';} else {lines[cy][cx] = '-';}}}for (auto& line : lines_) {std::cerr << line << '\n';}std::cerr.flush();}constexpr int MAX_L = 250000;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;const int k = std::max({2 * R / p + 1,R / (p * (R + 1) - q) + 1,(R + q - p * R - 1) / (q - p * R)});std::vector<std::pair<int, int>> points;// 山 ifor (int i = 0; i < R; ++i) {int x = i * (k * p + 1);int y = i;// 山 i を下るwhile (y > -R + i) {points.emplace_back(x, y);--y;}// 山 i と i+1 の間の谷の右端まで移動while (x < (i + 1) * (k * p - 1)) {points.emplace_back(x, y);++x;}// 山 i+1 を上るwhile (y < i + 1) {points.emplace_back(x, y);++y;}// 山 i+1 の峰の右端まで移動while (x < (i + 1) * (k * p + 1)) {points.emplace_back(x, y);++x;}}// 山 R{int x = R * (k * p + 1);int y = R;// 山 R を下るwhile (y > 0) {points.emplace_back(x, y);--y;}// (D,0) まで進むwhile (x <= k * q) {points.emplace_back(x, y);++x;}}int L = points.size() - 1;if ((MAX_L - L) % 2 == 1) {const int num = (MAX_L + 1 - L) / 2;std::vector<std::pair<int, int>> head;for (int i = 0; i < num; ++i) head.emplace_back(0, 0), head.emplace_back(0, -1);points.insert(points.begin(), head.begin(), head.end());}std::cout << points.size() - 1 << '\n';for (const auto& [x, y] : points) {std::cout << x << ' ' << y << '\n';}// debug(points);}