結果

問題 No.5009 Draw A Convex Polygon
ユーザー LanatusLanatus
提出日時 2022-12-02 17:56:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 163 ms / 2,600 ms
コード長 7,510 bytes
コンパイル時間 1,953 ms
実行使用メモリ 22,432 KB
スコア 178,880
平均クエリ数 178881.00
最終ジャッジ日時 2022-12-02 17:56:46
合計ジャッジ時間 3,141 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 163 ms
22,432 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define all(v) begin(v), end(v)
#define endl '\n'

using namespace std;

#define int long long

using ull = unsigned long long;
using ll  = long long;
using ld  = long double;

const int MOD = 1e9 + 7;
const int MAX = 2000005;

#pragma region Macros

template <class S, class T> inline bool chmax(S &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <class S, class T> inline bool chmin(S &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <class S> using pq  = priority_queue<S>;
template <class S> using pqg = priority_queue<S, vector<S>, greater<S>>;


struct mint {
  ull a;

  constexpr mint(const ull x = 0) noexcept : a(x % MOD) {}
  constexpr mint operator + (const mint rhs) const noexcept { return mint(*this) += rhs; }
  constexpr mint operator - (const mint rhs) const noexcept { return mint(*this) -= rhs; }
  constexpr mint operator * (const mint rhs) const noexcept { return mint(*this) *= rhs; }
  constexpr mint operator / (const mint rhs) const noexcept { return mint(*this) /= rhs; }
  constexpr mint &operator += (const mint rhs) noexcept {
    a += rhs.a;
    if (a >= MOD) a -= MOD;
    return *this;
  }
  constexpr mint &operator -= (const mint rhs) noexcept {
    if (a < rhs.a) a += MOD;
    a -= rhs.a;
    return *this;
  }
  constexpr mint &operator *= (const mint rhs) noexcept {
    a = a * rhs.a % MOD;
    return *this;
  }
  constexpr mint &operator /= (mint rhs) noexcept {
    ull exp = MOD - 2;
    while (exp) {
      if (exp % 2) *this *= rhs;
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  constexpr mint pow(const mint &a, ull n) noexcept {
    if (n <= 0) return 1;
    auto t = pow(a, n / 2);
    t = t * t;
    if (n & 1) t = t * a;
    return t;
  }
};


long long modpow(long long a, long long n, long long m = MOD) {
  if (n <= 0) return 1LL;
  if (n % 2LL) return a * modpow(a, n-1) % MOD;
  long long t = modpow(a, n/2);
  return t % MOD * t % MOD;
}


struct Combination {
  const int MAX = 2e5 + 5;
  vector<long long> fact, invfact;

  Combination() {
    fact.resize(MAX);
    invfact.resize(MAX);

    fact[0] = 1;

    for (int i = 1; i < MAX; ++i) {
      fact[i] = fact[i-1] * i % MOD;
    }

    invfact[MAX-1] = modpow(fact[MAX-1], MOD-2);

    for (int i = MAX-1; i > 0; --i) {
      invfact[i-1] = invfact[i] * i % MOD;
    }
  }

  long long nCr(int n, int r) {
    long long a = fact[n];
    long long b = invfact[r] * invfact[n-r] % MOD;

    return a * b % MOD;
  }
};


struct Node {
  int from, to;
  ll d;

  Node(int from, int to, ll d): from(from), to(to), d(d) {}
  Node(int to, ll d): from(-1), to(to), d(d) {}
  Node() {}
};

using Graph = vector<vector<Node>>;

struct LCA {
  int n, k;
  vector<vector<int>> parent;
  vector<int> depth;
  vector<ll> dis;
 
 
  LCA(const Graph& G, int root = 0) : n(G.size()) {
    k = 1;
    while ((1LL << k) < n) ++k;
 
    parent.assign(k, vector<int>(n, -1));
    depth.assign(n, -1);
    dis.assign(n, 0);
 
    dfs(G, root, -1, 0);
 
    for (int i = 0; i < k-1; ++i) {
      for (int j = 0; j < n; ++j) {
        if (parent[i][j] == -1) parent[i+1][j] = -1;
        else parent[i+1][j] = parent[i][parent[i][j]];
      }
    }
  }
 
  void dfs(const Graph& G, int v, int p, int d) {
    depth[v] = d;
    parent[0][v] = p;
 
    for (auto e : G[v]) {
      if (e.to == p) continue;
      dis[e.to] = dis[v] + e.d;
      dfs(G, e.to, v, d + 1);
    }
  }
 
  int query(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    int diff = depth[x] - depth[y];
 
    for (int i = 0; diff > 0; diff /= 2, ++i) {
      if (diff & 1) {
        x = parent[i][x];
      }
    }
 
    if (x == y) return x;
 
    for (int i = k-1; i >= 0; --i) {
      if (parent[i][x] != parent[i][y]) {
        x = parent[i][x];
        y = parent[i][y];
      }
    }
 
    return parent[0][x];
  }
 
  ll get_dis(int x, int y) {
    return dis[x] + dis[y] - 2 * dis[query(x, y)];
  }
  
  bool is_on_path(int x, int y, int a) {
    return get_dis(x, a) + get_dis(a, y) == get_dis(x, y);
  }
};

// 0-idx
struct RmaxQ {
  const ll INFLL = 1e18;
  int m;
  vector<long long> dat;
 
  RmaxQ(int n) {
    m = 1;
    while (m < n) m *= 2;
 
    dat.assign(2 * m - 1, -INFLL);
  }
 
  void update(int i, long long x) {
    i += m - 1;
    dat[i] = x;
 
    while (i) {
      i = (i - 1) / 2;
      dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);
    }
  }
 
  // [a, b)
  long long query(int a, int b, int k, int l, int r) {
    if (l >= b || r <= a) return -INFLL;
    if (a <= l && r <= b) return dat[k];
    
    long long vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    long long vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
 
    return max(vl, vr);
  }
 
  long long query_sub(int a, int b) {
    return query(a, b, 0, 0, m);
  }
};

struct RsumQ {
  const ll NIL = 0;
  int m;
  vector<long long> dat;
 
  RsumQ(int n) {
    m = 1;
    while (m < n) m *= 2;
 
    dat.assign(2 * m - 1, NIL);
  }
 
  void update(int i, long long x) {
    i += m - 1;
    dat[i] += x;
 
    while (i) {
      i = (i - 1) / 2;
      dat[i] = dat[i * 2 + 1] + dat[i * 2 + 2];
    }
  }
 
  // [a, b)
  long long query(int a, int b, int k, int l, int r) {
    if (l >= b || r <= a) return NIL;
    if (a <= l && r <= b) return dat[k];
    
    long long vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    long long vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
 
    return vl + vr;
  }
 
  long long query_sub(int a, int b) {
    return query(a, b, 0, 0, m);
  }
};

struct RminQ {
  const ll INFLL = 1e18;
  int m;
  vector<long long> dat;
 
  RminQ(int n) {
    m = 1;
    while (m < n) m *= 2;
 
    dat.assign(2 * m - 1, INFLL);
  }
 
  void update(int i, long long x) {
    i += m - 1;
    dat[i] = x;
 
    while (i) {
      i = (i - 1) / 2;
      dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);
    }
  }
 
  // [a, b)
  long long query(int a, int b, int k, int l, int r) {
    if (l >= b || r <= a) return INFLL;
    if (a <= l && r <= b) return dat[k];
    
    long long vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    long long vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
 
    return min(vl, vr);
  }
 
  long long query_sub(int a, int b) {
    return query(a, b, 0, 0, m);
  }
};

struct UnionFind {
  int n;
  vector<int> parent, siz;
 
  UnionFind(int n) : n(n) {
    parent.resize(n);
    siz.resize(n);
 
    for (int i = 0; i < n; ++i) {
      parent[i] = i;
      siz[i] = 1;
    }
  }
 
  int root(int x) {
    if (parent[x] == x) return x;
    return parent[x] = root(parent[x]);
  }
 
  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
 
    if (x == y) return false;
 
    if (siz[x] < siz[y]) swap(x, y);
    parent[y] = x;
    siz[x] += siz[y];
 
    return true;
  }
 
  int same(int x, int y) {
    return root(x) == root(y);
  }
 
  int size(int x) {
    return siz[root(x)];
  }
};

#pragma endregion

signed main(void) {
  int N = 44721;
  int x = 0, y = N * (N - 1) / 2;

  vector<pair<int,int>> p;
  p.push_back({x, y});

  for (int i = 1; i < N; ++i) {
    x -= (N - i);
    y -= i;

    p.push_back({x, y});
  }

  for (int i = 1; i < N; ++i) {
    x += i;
    y -= (N - i);

    p.push_back({x, y});
  }

  for (int i = 1; i < N; ++i) {
    x += (N - i);
    y += i;

    p.push_back({x, y});
  }

  for (int i = 1; i < N - 1; ++i) {
    x -= i;
    y += (N - i);

    p.push_back({x, y});
  }

  cout << p.size() << endl;
  for (auto [x, y] : p) cout << x << " " << y << endl;

  return 0;
}
0