QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#245009#7680. Subwayckiseki#WA 1ms3472kbC++203.8kb2023-11-09 17:50:292023-11-09 17:50:29

Judging History

你现在查看的是最新测评结果

  • [2023-11-09 17:50:29]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3472kb
  • [2023-11-09 17:50:29]
  • 提交

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]