結果

問題 No.2597 Yet Another Topological Problem
ユーザー suisen
提出日時 2023-11-22 16:48:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 4,350 bytes
コンパイル時間 857 ms
コンパイル使用メモリ 82,404 KB
最終ジャッジ日時 2025-02-17 23:02:07
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

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

// <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();
}
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;
// i
for (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';
}
std::cout << "This is an exessive output." << std::endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0