#573870 (C++17) No.1264 010

• 問題: No.1264 010
• ユーザー: Tsukasan_z46
• 提出日時: 2020-10-31 14:50:18
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 1,000 ms
• コード長: 13,853 bytes
• コンパイル時間: 2,343 ms
• コンパイル使用メモリ: 206,488 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-22 04:59:36
• 合計ジャッジ時間: 3,091 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB

ソースコード

#include <bits/stdc++.h>
// #include <atcoder/all>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
// using namespace atcoder;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;
// INF<int>
// INF<ll>
template<typename T>
const auto INF = numeric_limits<T>::max();
/////////////////////////////////////////////////////////////////////
// graph-template
// Graph<int> g(V); // int型、頂点数Vのグラフ
// Graph<ll> g(V); // ll型、頂点数Vのグラフ
// g.add_directed_edge(f, t, c); // 有向グラフの場合
// g.add_edge(f, t, c); // 無向グラフの場合
// g.read(M); // 辺の数M、0-indexed必要、重みなし、無向グラフの場合
// g.read(M, 0, true); // 辺の数M、0-indexed不要、重みあり、無向グラフの場合
// g.read(M, 0, true, true); // 辺の数M、0-indexed不要、重みあり、有向グラフの場合
// int N = g.size();
// Edges<int> es; es.emplace_back(from, to, cost); // Edges<int>で受け取る場合
/////////////////////////////////////////////////////////////////////
template<typename T = int>
struct Edge{
  int from, to; T cost; int idx;
  Edge() = default;
  Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx){}
  operator int() const {return to;}
};
template<typename T = int>
struct Graph{
  vector<vector<Edge<T> > > g;
  int es;
  Graph() = default;
  explicit Graph(int n) : g(n), es(0){}
  size_t size() const{
    return g.size();
  }
  void add_directed_edge(int from, int to, T cost = 1){ // 有向グラフ
    g[from].emplace_back(from, to, cost, es++);
  }
  void add_edge(int from, int to, T cost = 1){ // 無向グラフ
    g[from].emplace_back(from, to, cost, es);
    g[to].emplace_back(to, from, cost, es++);
  }
  void read(int M, int padding = -1, bool weighted = false, bool directed = false) {
    for(int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a += padding;
      b += padding;
      T c = T(1);
      if(weighted) cin >> c;
      if(directed) add_directed_edge(a, b, c);
      else add_edge(a, b, c);
    }
  }
};
template<typename T = int>
using Edges = vector<Edge<T> >;
template<typename T = int>
using Matrix = vector<vector<T> >;
/////////////////////////////////////////////////////////////////////
// BFS（幅優先探索）
// vector<int> dist = BFS(g, s);
// for(auto &i : BFS(g, s)){cout << i << endl;} // 最短距離だけを表示する場合 
/////////////////////////////////////////////////////////////////////
template<typename T>
vector<T> BFS(const Graph<T> &g, int s) {
  T max_cost = 0, beet = 0;
  for(auto &es : g.g) {
    for(auto &e : es) max_cost = max(max_cost, e.cost);
  }
  ++max_cost;
  const auto INF = numeric_limits<T>::max();
  vector<T> dist(g.size(), INF);
  vector<queue<int> > ques(max_cost + 1);
  dist[s] = 0;
  ques[0].emplace(s);
  for(T cost = 0; cost <= beet; cost++) {
    auto &que = ques[cost % max_cost];
    while(!que.empty()) {
      int idx = que.front();
      que.pop();
      if(dist[idx] < cost) continue;
      for(auto &e : g.g[idx]) {
        auto next_cost = cost + e.cost;
        if(dist[e.to] <= next_cost) continue;;
        dist[e.to] = next_cost;
        beet = max(beet, dist[e.to]);
        ques[dist[e.to] % max_cost].emplace(e.to);
      }
    }
  }
  return dist;
}
/////////////////////////////////////////////////////////////////////
// ダイクストラ法（Dijkstra）法(単一始点最短路・負の辺がない場合)
// ShortestPath<int> SP = dijkstra(g, s); // グラフgと始点sを渡すと、全頂点への最短距離を返す
// ShortestPath<ll> SP = dijkstra(g, s);
// for(auto &i : dijkstra(g, r).dist){cout << i << endl;} // 最短距離のみを出力する
// ABC012D, ABC035D
/////////////////////////////////////////////////////////////////////
template<typename T>
struct ShortestPath{
  vector<T> dist;
  vector<int> from, id;
};
template<typename T>
ShortestPath<T> dijkstra(const Graph<T> &g, int s){
  const auto INF = numeric_limits<T>::max();
  vector<T> dist(g.size(), INF);
  vector<int> from(g.size(), -1), id(g.size(), -1);
  using Pi = pair<T, int>;
  priority_queue<Pi, vector<Pi>, greater<> > que;
  dist[s] = 0;
  que.emplace(dist[s], s);
  while(!que.empty()){
    T cost;
    int idx;
    tie(cost, idx) = que.top();
    que.pop();
    if(dist[idx] < cost) continue;
    for(auto &e : g.g[idx]){
      auto next_cost = cost + e.cost;
      if(dist[e.to] <= next_cost) continue;
      dist[e.to] = next_cost;
      from[e.to] = idx;
      id[e.to] = e.idx;
      que.emplace(dist[e.to], e.to);
    }
  }
  return {dist, from, id};
}
/////////////////////////////////////////////////////////////////////
// ベルマンフォード（Bellman-Ford）法(単一始点最短路・負の辺を含む場合)
// Edges<T>を受け取る（Graph<T>ではない。）
// Edges<int> es; es.emplace_back(from, to, cost);
// vector<int> dist = bellman_ford(es, V, s);
// vector<ll> dist = bellman_ford(es, V, s);
// 到達できないときはINF<T>を返す。負閉路を検出したときは、空の数列を返す。
// if(dist.empty()){ } // 負閉路を検出した場合の処理
/////////////////////////////////////////////////////////////////////
template<typename T>
vector<T> bellman_ford(const Edges<T> &edges, int V, int s) {
  const auto INF = numeric_limits<T>::max();
  vector<T> dist(V, INF);
  dist[s] = 0;
  for(int i = 0; i < V - 1; i++){
    for(auto &e : edges){
      if(dist[e.from] == INF) continue;
      dist[e.to] = min(dist[e.to], dist[e.from] + e.cost);
    }
  }
  for(auto &e : edges){
    if(dist[e.from] == INF) continue;
    if(dist[e.from] + e.cost < dist[e.to]) return vector<T>();
  }
  return dist;
}
/////////////////////////////////////////////////////////////////////
// ワーシャルフロイド（WarshallFloyd）法（全点最短経路）
// 隣接行列で表されるグラフの全点間最短路を求めるアルゴリズム。負辺があっても動作する。
// 負閉路が存在する場合はそれも検出する(ある頂点kからkへの最短路が負ならば負閉路が存在)。
// Matrix<int> mat(V, vector<int>(V, INF<int>)); REP(i, V) mat[i][i] = 0; // 初期化
// mat[i][j] = cost;
// warshall_floyd(mat, INF<int>);
/////////////////////////////////////////////////////////////////////
template<typename T>
void warshall_floyd(Matrix<T> &g, T INF) {
  for(int k = 0; k < g.size(); k++) {
    for(int i = 0; i < g.size(); i++) {
      for(int j = 0; j < g.size(); j++) {
        if(g[i][k] == INF || g[k][j] == INF) continue;
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
}
/////////////////////////////////////////////////////////////////////
// べき乗（mod-pow）
// ll res = modpow(x, n); // x^n mod 1e9+7の答えを返す
// ll res = modpow(x, n, 998244353) // x^n mod 998244353の答えを返す
/////////////////////////////////////////////////////////////////////
template<typename T>
T modpow(T x, T n, const T p = 1e9+7){
  T res = 1;
  while(n > 0) {
    if(n & 1) (res *= x) %= p;
    (x *= x) %= p;
    n >>= 1;
  }
  return res;
}
/////////////////////////////////////////////////////////////////////
// FacPrimeNum（階乗に含まれる素因数の個数）
// int cnt = FacPrimeNum(n, p) // n!に含まれる素数pの個数を返す
// n!の末尾には、0が連続して何個並ぶか？ FacPrimeNum(n, 5)
// 2^kがn!を割り切るような最大の自然数kは？　FacPrimeNum(n, 2)
// トリッキー問題コンテスト C - 階乗と素因数
/////////////////////////////////////////////////////////////////////
template<typename T = ll>
T FacPrimeNum(T n, T p){
  T res = 0;
  T tmp = p;
  while(n/tmp > 0){
    res += n/tmp;
    tmp *= p;
  }
  return res;
}
/////////////////////////////////////////////////////////////////////
// Divisor（約数列挙）
// vector<ll> div = divisor(N);
/////////////////////////////////////////////////////////////////////
template<typename T = ll>
vector<T> divisor(T n) {
  vector<T> ret;
  for(T i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}
/////////////////////////////////////////////////////////////////////
// isPrime（素数判定）
// bool ip = isPrime(N); // Nが素数ならtrue、素数でなければfalseを返す
/////////////////////////////////////////////////////////////////////
template<typename T = ll>
bool isPrime(T n){
  if(n <= 1) return false;
  if(n == 2) return true;
  if(n % 2 == 0) return false;
  for(T i = 3; i*i <= n; i += 2){
    if(n % i == 0) return false;
  }
  return true;
}
/////////////////////////////////////////////////////////////////////
// PrimeFactor（素因数分解）
// auto MP = Prime_Factor(N);
// for(auto i : MP){
//   cout << i.first << " " << i.second << endl;
// }
/////////////////////////////////////////////////////////////////////
template<typename T = ll>
map<T, T> Prime_Factor(T n){
  map<T, T> mp; T cnt = 0;
  while(n%2 == 0){
    n /= 2; cnt++;
  }
  if(cnt != 0) mp[2] = cnt;
  for(T i = 3; i*i <= n; i += 2){
    cnt = 0;
    while(n%i == 0){
      n /= i; cnt++;
    }
    if(cnt != 0) mp[i] = cnt;
  }
  if(n != 1) mp[n] = 1;
  return mp;
}
/////////////////////////////////////////////////////////////////////
// ModInt（mod Mでの四則演算を行う構造体）
// ModInt a = N;
/////////////////////////////////////////////////////////////////////
template<int mod>
struct ModInt{
  int x;
  ModInt() : x(0) {}
  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int) (1LL * x * p.x % mod);
    return *this;
  }
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }
  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
  bool operator==(const ModInt &p) const { return x == p.x; }
  bool operator!=(const ModInt &p) const { return x != p.x; }
  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0){
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  ModInt pow(int64_t n) const{
    ModInt ret(1), mul(x);
    while(n > 0){
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  friend ostream &operator<<(ostream &os, const ModInt &p){
    return os << p.x;
  }
  friend istream &operator>>(istream &is, ModInt &a){
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }
  static int get_mod() { return mod; }
};
/////////////////////////////////////////////////////////////////////
// Union-Find木：グループ分けを管理するデータ構造
// UnionFind tree(N);でUnion-Find木を生成
// tree.leader(X);で親ノード番号を返す
// tree.merge(X, Y);でノードを結合する
// tree.same(X, Y);でXノード、Yノードが結合しているかどうか返す（bool型）
// tree.size(X);でXノードが結合しているノード数を返す
/////////////////////////////////////////////////////////////////////
struct UnionFind{
  vector<int> par;
  vector<int> sizes;
  UnionFind(int N) : par(N), sizes(N, 1){
    for(int i = 0; i < N; i++) par[i] = i;
  }
  int leader(int x){
  if(par[x] == x) return x;
    return par[x] = leader(par[x]);
  }
  void merge(int x, int y){
    int rx = leader(x);
    int ry = leader(y);
    if(rx == ry) return;
    if(sizes[rx] < sizes[ry]) swap(rx, ry);
    par[ry] = rx;
    sizes[rx] += sizes[ry];
  }
  bool same(int x, int y){
    int rx = leader(x);
    int ry = leader(y);
    return rx == ry;
  }
  int size(int x){
    return sizes[leader(x)];
  }
};
/////////////////////////////////////////////////////////////////////
// 最長共通部分列（LCS）
// 2つの文字列の「部分文字列」の中で最長の長さのもの。順序を変更してはいけない
// int ans = LCS(S, T); // 文字列SとTの最長共通部分列の文字数を返す
// 計算量 O(NM)
/////////////////////////////////////////////////////////////////////
int LCS(string s, string t){
  int n = s.size(), m = t.size();
  s += '$'; t += '%';
  vector<vector<int> > dp(n+2, vector<int>(m+2, -(n+m)));
  dp[0][0] = 0;
  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= m; j++){
      chmax(dp[i+1][j], dp[i][j]);
      chmax(dp[i][j+1], dp[i][j]);
      chmax(dp[i+1][j+1], dp[i][j]+(s[i]==t[j]));
    }
  }
  return dp[n][m];
}
/////////////////////////////////////////////////////////////////////
// 初期設定
/////////////////////////////////////////////////////////////////////
const int mod = 1000000007;
const ll MOD = 998244353;
const int dx[] = { 1,  0, -1,  0};
const int dy[] = { 0,  1,  0, -1};
using modint = ModInt<mod>;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ////////////////////////////////// コード //////////////////////////////////
  int N; cin >> N;
  if(N == 0){
    cout << "01" << '\n';
  }else if(N == 1){
    cout << "010" << '\n';
  }else{
    cout << "010";
    REP(i, N-1){
      cout << "0";
    }
    cout << '\n';
  }
}