QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#245009 | #7680. Subway | ckiseki# | WA | 1ms | 3472kb | C++20 | 3.8kb | 2023-11-09 17:50:29 | 2023-11-09 17:50:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(const char *s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
void orange_(const char *s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
for (int f = 0; L != R; L++)
cerr << (f++ ? ", " : "") << *L;
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
class SVG {
void p(string_view s) { o << s; }
void p(string_view s, auto v, auto... vs) {
auto i = s.find('$');
o << s.substr(0, i) << v, p(s.substr(i + 1), vs...);
}
ofstream o;
string c = "red";
public:
SVG(auto f, auto x1, auto y1, auto x2, auto y2) : o(f) {
p("<svg xmlns='http://www.w3.org/2000/svg' viewBox='$ $ $ $'>\n"
"<style>*{stroke-width:0.5%;}</style>\n",
x1, -y2, x2 - x1, y2 - y1);
}
~SVG() { p("</svg>\n"); }
SVG &color(string nc) { return c = nc, *this; }
void line(auto x1, auto y1, auto x2, auto y2) {
p("<line x1='$' y1='$' x2='$' y2='$' stroke='$'/>\n",
x1, -y1, x2, -y2, c);
}
};
constexpr int R = 1'000'000'000;
using lld = int64_t;
void exgcd(lld x, lld y, lld &a, lld &b) {
if (y == 0) a = 1, b = 0;
else exgcd(y, x % y, b, a), b -= (x / y) * a;
}
pair<lld, lld> MakeMid(lld a, lld b, lld v) {
lld x, y;
exgcd(a, b, x, y);
lld vv = v % abs(a);
x *= vv, y *= vv;
return {x + v / abs(a), y};
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
mt19937 rnd(7122);
uniform_int_distribution<lld> C(-10'000, 10'000);
int n;
cin >> n;
vector<tuple<lld, lld, int>> v_(n);
for (auto &[x, y, c] : v_)
cin >> x >> y >> c;
while (true) {
lld a = C(rnd), b = C(rnd);
if (a == 0 and b == 0)
continue;
lld g = gcd(abs(a), abs(b));
a /= g, b /= g;
auto v = v_;
auto f = [&](lld x, lld y) {
return a * x + b * y;
};
sort(v.begin(), v.end(), [&](const auto &lhs, const auto &rhs) {
return f(get<0>(lhs), get<1>(lhs)) < f(get<0>(rhs), get<1>(rhs));
});
bool valid = true;
for (int i = 1; i < n; ++i) {
valid &= f(get<0>(v[i]), get<1>(v[i])) - f(get<0>(v[i - 1]), get<1>(v[i - 1])) > 1;
}
if (not valid)
continue;
vector<pair<lld, lld>> mid;
for (int i = 0; i + 1 < n; ++i) {
const auto [x1, y1, _] = v[i];
lld fv = f(x1, y1) + 1;
auto [x2, y2] = MakeMid(a, b, fv);
mid.emplace_back(x2, y2);
}
vector<vector<pair<lld, lld>>> ans;
while (true) {
bool all0 = true;
for (auto [_, __, c] : v)
all0 &= c == 0;
if (all0)
break;
ans.push_back({});
for (int i = 0; i < n; ++i) {
auto &[x, y, c] = v[i];
if (c == 0) {
x -= b, y += a;
} else {
c -= 1;
}
ans.back().emplace_back(x, y);
if (i + 1 < n) {
ans.back().push_back(mid[i]);
mid[i].first -= b;
mid[i].second += a;
}
}
}
for (const auto &ansi : ans) {
for (auto [x, y] : ansi) {
valid &= -R <= x and x <= R;
valid &= -R <= y and y <= R;
}
}
if (not valid)
continue;
//SVG svg("d.svg", -1e5, -1e5, 1e5, 1e5);
cout << ans.size() << '\n';
for (const auto &ansi : ans) {
cout << ansi.size();
for (auto [x, y] : ansi) {
cout << ' ' << x << ' ' << y;
}
cout << '\n';
//for (size_t i = 1; i < ansi.size(); ++i) {
// auto [x1, y1] = ansi[i - 1];
// auto [x2, y2] = ansi[i];
// svg.line(x1, y1, x2, y2);
//}
}
break;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3452kb
input:
3 1 2 1 2 1 2 3 3 2
output:
2 5 1 2 -21420 -32040 3 3 63665 95230 2 1 5 360 539 -21061 -31503 3 3 64024 95767 2 1
result:
ok ok Sum L = 10
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3472kb
input:
1 1 1 1
output:
1 1 1 1
result:
wrong answer Integer parameter [name=L] equals to 1, violates the range [2, 10000]