結果
問題 | No.2597 Yet Another Topological Problem |
ユーザー |
|
提出日時 | 2023-11-22 16:34:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 4,388 bytes |
コンパイル時間 | 793 ms |
コンパイル使用メモリ | 82,400 KB |
最終ジャッジ日時 | 2025-02-17 23:01:43 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
// 単純でないが制約を満たす曲線#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();}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;points.emplace_back(0, 0);points.emplace_back(0, -1);// 山 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;}}std::cout << points.size() - 1 << '\n';for (const auto& [x, y] : points) {std::cout << x << ' ' << y << '\n';}// debug(points);}