HackerRankのがっぽコンについて+Bitcoinの使い道

はじめに

この記事はCompetitive Programming (その2) Advent Calendar 2016 - Adventarの3日目の記事です。(遅れてしまいすみませんでした。)

皆様はHackerRankというコンテストサイトをご存知でしょうか。12/4現在、日本人登録者が490名で、他コンテストサイトに比べると国内ではまだまだ知名度が低そうです。

HackerRankでは様々なコンテストが開かれています:

  • 1~2時間の短時間コンテスト(HourRank, 101 Hack)
  • 1~3日のコンテスト(Codesprint, Ad Infinitum)
  • 1週間に渡って毎日問題が追加されていくコンテスト(Week of Code)など。

また、コンテスト以外にも、特定のプログラミング言語正規表現等様々なジャンルの学習にも使える教材がたくさんあるようです。(こちらは使ったことがないため、内容については分かりません。)

賞品つきコンテスト(通称:がっぽコン)

HackerRankではCodesprintと呼ばれる24-48時間コンテストが1-2ヶ月に1度くらい開催されていて、100位以内に入れば賞金(75ドル)とTシャツがもらえます。

前述のとおり知名度があまり高くないためか、100位以内を目指すのは他コンテストに比べて楽です。

賞金自体はBitcoinで送金されていますが、日本人参加者の感想を見ていると、Bitcoinをもらっても使い道に困る(hackos並にどうでもいい)、換金には海外口座がいるらしい、など色々な発言を見かけました。

普通にお金でもらうより使い所が限られていて不便そうですが、調べてみると意外と使い所があります。

Bitcoinの使い道の一例

使い道1: 食事

支払いにBitcoinが使えるお店が国内にいくつかあります。参考: ビットコインが使える日本のお店

実際にBitcoinでの支払いを試すのも兼ねて、にくがとうというお店に行きました。

お店のレビューはさておき(おいしかったです)、Bitcoinでの支払いはとても簡単で、QRコードスマホで読み込むだけでした。

Bitcoinで支払う物好きな客は月に1,2人とのことでしたので、事前にBitcoinで支払う旨を伝えておいたほうがスムーズに会計が進んで良いと思います。

使い道2: ゲーム

SteamはBitcoinによる支払いに公式で対応しています。指定されたアドレスに指定されたBTCを送るだけで簡単にウォレットにチャージできます。

三が日までウィンターセールが開催されているので、今は買い時ですね。自分が買ってよかったと思うゲームを少し挙げます。

  • La-Mulana
    • 謎解き+アクション、どちらも難しくやりごたえがかなりある。セール中こんなにすごいゲームがコンビニ弁当より安く買えてしまってよいのだろうかと逆に申し訳なくなるレベル。
  • Crypt of Necrodancer
    • テンポに合わせて行動するローグライク。中毒性が高い。キャラクター別(10種くらい)で難易度がぜんぜん異なるので幅広く楽しめそう。
  • Sid Meier's Civilization® V
    • 文明の主導者となって、開拓したり他文明と交流しつつ勝利を目指すゲーム。セール中にDLCとまとめて買うのがよさそう。秋セールで一緒に買った人達が皆休日を溶かしてしまい、危険。

他にも面白そうなゲームはたくさんあるので、色々探してみるのも面白そうですね。

使い道3: 換金する

食事にもゲームにもあまり気が進まない方に朗報ですが、普通に換金できます。国内の口座に振り込んでくれる取引所を使います。私はcoincheckを使いました。

BTCで入金後、取引所で日本円に変えた後に自分の銀行口座に振り込みます。アカウント登録が必要だったり、振込手数料がかかったりはしますが、あまり手間はかからなかったように思います。

さらに野心のある方はcoincheck上でBitcoinでFXをすることもできます。私はFXでGTX1080を買う資金を捻出しようとして、逆にGTX1080相当以上の損失をしてしまったので、人におすすめはしません。なかなかうまくいかないものですね。

おわりに

  • HackerRankのがっぽコンでがっぽがっぽしましょう。
  • これからBitcoinの価値がどうなるか分かりませんが、幸いにも今は過去最高レベルで価値が高い状態なので、忘れていた方は使ってみてもいいかもしれませんね。

いろんな人のテンプレートを観察

この記事はCompetitive Programming Advent Calender(その2) 23日目の記事です。

はじめに

競技プログラミングでいろんな人のコードを読んでみると、前半部分には人によって色々なマクロや関数が定義されていたりいなかったりします。(参考: Quora)

この部分にはその人が快適にコーディングするための工夫が見られて面白いので、今回いろんな人のテンプレートを眺めてみることにしました。

実際に見たテンプレートはここ(Codeforces)ここ(KUPC)にまとめました。時間の都合上、それぞれ約50人、約30人しか見ていません。しかも途中で疲れてコメントがかなり雑です。すいません。

これらを見てどのような機能がテンプレートにあったか挙げていきたいと思います。

※この記事は競技プログラミングにある程度参加している人が読者であることを想定しています。そうではなくて、どうしてこんなものを使うの?と疑問がある方は、インターネットで検索するとQuoraにある質問等がヒットしますので、そちらを御覧ください。それでも尚分からない方にとっては、記事の内容が不健全に見えるでしょうから、注意して下さい。


よく見かける定番機能

指定回数ループして現時点の回数も分かるrepマクロ

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

定番のrepマクロです。マクロなので作法として大文字にする人がいたり、よく使うし最早rep文なので小文字にする人がいたりします。

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

これはnatsugiriさんのテンプレートから引用しました。repを使う時はほとんどの場合で第二引数の値が変わらないことを前提として使われますが、第二引数が何らかの関数(vectorのsize()とか)である場合にいちいち呼ぶと、例えそれがO(1)のsize()であっても、ループ回数が非常に多い場合はTLEしてしまう事が過去にありました。 これを避けるのが上記のマクロで、二重repの場合でもrepの第一引数に同じ名前の変数を使わない限りは変数名が被っていると怒られることはありません。

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};

こちらはrepマクロではないですが、機能が似ているのでここで紹介します。pythonのrangeみたいなものをC++でも扱うことができます。これはir5先生のテンプレートから引用しました。repマクロですが、冷静になると変数の宣言を一切してない点が気持ち悪いです。rangeクラスを使えば、変数を宣言していない問題は解決されます。

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

こちらは可変長引数のrepマクロです。repの引数が2つの場合と3つの場合で_overload3のnameが変わって挙動が変わります。(すごい) stqnさん、evimaさんのテンプレートにありました。

もう全部だしallマクロ

#define all(x) (x).begin(),(x).end()

sortやlower_boundする時に先頭と末尾のイテレータを渡すことはよくありますが、あまりにも頻出なためマクロで一纏めにしておくと便利です。

型名長杉、省略させて

using ll = long long;
typedef long long ll;
typedef long long int64;
typedef long long lint;
typedef long long lli;

long longはあまりにも頻出なので、もっと打ちやすく見た目もよい型名にエイリアスしている人が多いです。C++11から一番上みたいな記法もできるようになりました。 私事ですいません、自分はlint派なのですが、skyさんもlint派で感激しました。国内外問わずll派が圧倒的に多く、海外ではint64派も存在します。lintにしてるのは打ちやすさとintっぽさを残したかったからです。

size()がunsignedでつらい

#define SZ(x) ((int)(x).size())

unsignedなので加減算して思わぬバグを踏むことがあったり、intが絡む計算をするといちいち警告が出たりするので、それらを防ぐ目的のマクロです。

好みが分かれる機能

memsetマクロ

#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define clr(ar,val) memset(ar, val, sizeof(ar))
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMSET(v, h) memset((v), h, sizeof(v))

いろんな人がいろんな名前でmemset絡みのマクロを作っています。 配列を何かで埋めたい場合に使う事が多いmemsetですが、第一引数と第三引数に大抵同じものを書くことになるので、マクロにするのも一つの手です。 埋める内容も大抵0, -1, 0x3fの3通りなので、それら毎にマクロを作ってもいいかもしれません。

デバッグ出力マクロ

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

手元の環境でのみLOCALをdefineしておいて、上のように書くと手元ではデバッグ出力が見えて、ジャッジサーバーでの実行時には(LOCALが定義されていない限り)出力されません。 コンパイルオプションに-Dhogehogeとするとhogehogeがdefineされます。 海外勢のテンプレートでは上のようなeprintfをよく見かけましたが、それ以外にも手元の環境でのみデバッグ出力用の関数が書かれたヘッダをインクルードして使う人もいます。

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif

最大値、最小値を更新する関数

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

sune2さんのテンプレートからの引用です。

if(hoge < fuga + piyo) hoge = fuga + piyo;

みたいなコードを書くと同じ部分が2箇所出てきて、配列の添字などが絡んでくると同じものを2つ書きたくないので、更新用の関数があると便利です。 また、値が更新された時に限りtrueを返すようにしておけば、例えばDPの経路を復元したい場合にきれいに書けます。

名前も色々付け方があり、umax(update?), amax(assign) とかにしている人がいます。

長いのは全部短く

#define pcnt __builtin_popcount

#define buli(x) __builtin_popcountll(x)

#define pb push_back
#define mp make_pair

#define F first
#define S second

いろんな人からの引用です。 この辺はかなり好みが分かれますが、長いと打つのにも時間がかかるので、短く省略するのも一つの手です。

名前が被るのが嫌

#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev

いろんな人からの引用です。 y0等は標準ライブラリ関数として存在しているので、変数名にy0等を使うと怒られます。それを避けるためにy0等を別の名前に置き換えます。

自前の入出力関数

AOJだと、readで全部入力を読んで自分でパースすると、入力が非常に大きい時には実行速度が結構速くなります。 getcharなどを使って入力を読んでパースしている人も少数ですが存在します。こだわりが垣間見えます。

確かに、scanfはやや長いし、cinは速度面で不満があるので、このような関数を自前で準備するのは一つの手です。

repの変種

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

zerokugiさんのテンプレートから引用です。名前は異なりますが同じようなマクロはそこそこ見かけました。zerokugiさんの場合は頭にRつけると逆向き、最後にSつけると1-originになるみたいです。

#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

これは私のテンプレートからの引用です。順列を全通り試したい時に使います。

あると便利な機能は一応入れる

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

jcvbさんから引用、冪乗計算やgcdやdxdyが必要な時にいちいち書かなくて済むという利点があります。

void precalc() {

    /*for (int i = 2; i < C; ++i) {
       if (!least_prime[i]) {
           least_prime[i] = i;
           for (li j = i * 1LL * i; j < C; j += i) {
               least_prime[j] = i;
           }
       }
   }*/

    /*fact[0] = revfact[0] = 1;
   for (int i = 1; i < 100500; ++i) {
   fact[i] = fact[i - 1] * i % curMod;
   revfact[i] = binpow(fact[i], curMod - 2, curMod);
   }*/

    /*for (int w = 0; w < 2; ++w) {
   powers[w][0] = 1;
   for (int j = 1; j < C; ++j) {
   powers[w][j] = (powers[w][j - 1] * 1LL * pr[w]) % mods[w];
   }
   }*/

    /*catalan[0] = 1;
   for (int n = 0; n < 200500 - 1; ++n) {
   catalan[n + 1] = catalan[n] * 2 * (2 * n + 1) % MOD * binpow(n + 2, MOD - 2, MOD) % MOD;
   }*/

    /*for (int i = 0; i < 5010; ++i) {
   c[i][i] = c[i][0] = 1;
   for (int j = 1; j < i; ++j) {
   c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
   }
   }*/

    /*for (int i = 0; i < 100; ++i) {
   doubleC[i][i] = doubleC[i][0] = 1.0;
   for (int j = 1; j < i; ++j) {
   doubleC[i][j] = doubleC[i - 1][j - 1] + doubleC[i - 1][j];
   }
   }*/
}

Kostromaさんから引用です。precalcの中に素数篩、階乗とあるmodでのその逆元、カタラン数、二項係数などがあり、アンコメントすることで使えるようになっています。

突き詰めるとライブラリを全部貼るのが一番便利なのかもしれません。

マイナーだけど面白いと思った機能

cauto

#define cauto const auto&

climpetさんのテンプレートからの引用です。結構使うのであると便利そうです。

bit(x)

#define bit(n) (1LL<<(n))

Mi_Sawaさんのテンプレートからの引用です。ビット演算の優先順序は正直覚えてなくて、書くといっつも括弧だらけになるし、たまにLLを忘れるので、あると便利そうです。

uniqueどうやるんだっけ?

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

zerokugiさんのテンプレートからの引用です。 長いし、(私は使い方を忘れるので、)マクロにしておくのも一つの手です。

打ち間違えても安心

#define itn int

Golovanov399さんから引用です。打ち間違いを直す時間すら惜しい。

最後は神頼み

f:id:ehafib:20151223165244p:plain

引用元

提出したコードにバグがないことを祈り、バグを踏むケースがないことを祈りましょう。 hackしようとして開いていきなりこれが表示されると、なかなかインパクトを受けます。

その他

たまに見かけるおまじない

#pragma comment (linker, "/STACK:256000000")

スタック領域を拡張するおまじないだそうですが、MSVC++でしか効果がないそうです。

#define _CRT_SECURE_NO_WARNINGS

これもMSVC++だとscanf等のセキュリティが弱い古い関数を使った時の警告を抑制する効果があるそうですが、GNU g++ではおそらく無意味です。

#define _USE_MATH_DEFINES

これもMSVC++だとM_PIが使えるようになるらしいです。

ヘッダ

#include <bits/stdc++.h>

GNU g++でのみ使えるヘッダで、中はこうなっています。

大抵のマシンでは<bits/stdc++.h>で全部インクルードしても問題ないのですが、ICPC等でマシン環境がポンコツだった場合にこれをするとコンパイルに時間がかかるので注意が必要です。

やや脱線しますが、gnu g++では__gcd()stl_algo.h内で定義されているから自分でgcdは書かなくてもよいことはよく知られていますが、__lg()という関数もあります。こちらは例えばセグメントツリーを作る時の配列のサイズを計算する時などに短く書けたりします。ここで挙げた機能は全てC++標準の機能ではありません。

main関数より先に呼びたい関数がある場合

例えばcin高速化などをしたい時など、main関数の冒頭部で必ず呼ぶ関数は別の箇所にまとめて記述することもできます。

struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
}aaaaaaa;

こういう構造体を実際に作ることでコンストラクタが呼ばれ、main関数より先に実行されます。

テンプレートが長すぎて見た目によくない場合

大抵のエディタには折りたたみ機能がついているのでそれで畳んであげると見た目はよくなります。

テンプレートの中身をあまりに常用するのでシンタックスハイライトで色を付けたい場合

私と同じエディタを使っている場合、私の設定がこちらにありますので、参考になるか分かりませんがご自由にお使い下さい。

デバッグ出力の見た目をよくしたい場合

f:id:ehafib:20151223165303p:plain

私は(こんな感じ1), (こんな感じ2)デバッグ用出力関数を書いてますが、まだ試行錯誤している段階です。便利そうなデバッグ出力の方法をご存知の方はどうか教えて下さい。

おわりに

明日はuvarimeronさんによる「実際に日常生活で役立った競技プログラミング」です。伊東家の食卓もびっくりなやつを期待しています。

2/24追記: コード片を着色・注意書きを追加

テンプレート観察メモ(KUPC)

敬称略、KUPC2015の提出(CFで見た人除く)、まとめはこちら

kawatea

#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;
  • なし

yutaka1999

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <map>
#include <stack>
#include <set>
#include <string>
#include <cmath>
#define SIZE 105
 
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
  • ll派

zerokugi

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <unordered_map>
#include <iterator>
#include <functional>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
 
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
 
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}
 
const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;
  • ll派
  • pairの足し算引き算
  • chmax, chmin
  • REPマクロ、頭にRつけると逆向き、最後にSつけると1-origin
  • uniqueは一連の操作をマクロに

sugim48

#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
int INF = INT_MAX / 3;
double EPS = 1e-10;
  • 一行目はMSVC++だとM_PIが使えるようになる、他に意味があるかは不明
  • repなし
  • ll派
  • MODが1e9+7と1e9+9の二種類をサポート

stqn

#include <bits/stdc++.h>
using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
  • repが引数の個数で変わる(2引数だと0からn-1, 3引数だとaからb-1) すごい

tomerun

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>
#include <sys/time.h>
 
using namespace std;
typedef long long ll;
  • ll派

__math

#define _CRT_SECURE_NO_DEPRECATE
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <limits>
#include <ctime>
#include <cassert>
#include <map>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <stack>
#include <queue>
#include <numeric>
#include <iterator>
#include <bitset>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
 
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
 
template<typename ...> static inline int getchar_unlocked(void) { return getchar(); }
template<typename ...> static inline void putchar_unlocked(int c) { putchar(c); }
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
void reader(ll& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
template <class T, class S> void reader(T& x, S& y) { reader(x); reader(y); }
template <class T, class S, class U> void reader(T& x, S& y, U& z) { reader(x); reader(y); reader(z); }
template <class T, class S, class U, class V> void reader(T& x, S& y, U& z, V & w) { reader(x); reader(y); reader(z); reader(w); }
void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(ll x, char c) { int s = 0, m = 0; char f[20]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(const char c[]) { int i; for (i = 0; c[i] != '\0'; i++)mypc(c[i]); }
void writer(const char x[], char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
template<class T> void writerLn(T x) { writer(x, '\n'); }
template<class T, class S> void writerLn(T x, S y) { writer(x, ' '); writer(y, '\n'); }
template<class T, class S, class U> void writerLn(T x, S y, U z) { writer(x, ' '); writer(y, ' '); writer(z, '\n'); }
template<class T> void writerArr(T x[], int n) { if (!n) { mypc('\n'); return; }FOR(i, n - 1)writer(x[i], ' '); writer(x[n - 1], '\n'); }
  • 一番上はscanf等の警告抑制?GNU g++で効果あるかは不明
  • ll派
  • 入出力が高速化されてそう

logicmachine

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
 
using namespace std;
typedef long long ll;
  • ll派

mamekin

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;
  • なし

snuke

#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rrep(i,n) for(int i = 1; i <= n; ++i)
#define drep(i,n) for(int i = n-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}

const int MX = 100005, INF = 1000010000;
const ll LINF = 1000000000000000000ll;
const double eps = 1e-10;
  • rep, rrep, drep
  • rngがいわゆるall
  • snukeがsrand
  • __builtin_popcount は確かに長い、pcnt
  • ll派
  • df(x)がxをintとして宣言して入力もとる

yuusti

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <queue>
#include <tuple>
#include <numeric>
#include <sstream>
#include <cassert>
 
using namespace std;
  • なし

こくりつくるめどうぶつえん

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define int long long
  • 一番下はオーバーフローを防ぐ最終兵器

nisshy

// * template
 
#include <bits/stdc++.h>
#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
 
using namespace std;
 
template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }
 
template<class T, class U> inline void fill_array(T &e, const U &v) { e = v; }
template<class T, class U, size_t s> inline void fill_array(T (&a)[s], const U &v) {for(auto&e:a)fill_array(e,v);}
template<class T, class U, size_t s> inline void fill_array(array<T, s> &a, const U &v) {for(auto&e:a)fill_array(e,v);}
template<class T, class U> inline void fill_array(vector<T> &a, const U &v) {for(auto&e:a)fill_array(e,v);}
  • 手元でのみdump.hppをincludeしてデバッグ出力用のdump関数を使えるように
  • 各種埋め関数

sky58

#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define N 262144
  • lint派だ!!(握手)

yuizumi

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
  • なし

hongrock

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
 
int T;
typedef long long LL;
  • LL派

Mi_Sawa

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define repsz(i,v) rep(i,(v).size())
#define aur auto&
#define bit(n) (1LL<<(n))
#define eb emplace_back
#define mt make_tuple
#define fst first
#define snd second
using namespace std;
typedef long long ll;
//#define int long long
template<class C>int size(const C &c){ return c.size(); }
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}
  • bit(n) でn番目のbit, bitwise演算子の優先順序を全く覚えてないから括弧だらけになるし欲しい
  • 最終兵器をいつでも発動できるようにコメントアウトしている
  • chmin, chmax

kmjp

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
 
#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<to;x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------
  • _Pがデバッグ出力用
  • ZERO, MINUS がmemsetで0, -1埋め

(team)kirutos

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
  • lli派
  • IINF, LINF

evima

// Enjoy your stay.
 
#include <bits/stdc++.h>
 
#define long long long
#define LOOPVAR_TYPE long
 
#define all(x) (x).begin(), (x).end()
#define sz(x) ((LOOPVAR_TYPE)(x).size())
#define foreach(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++)
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i, n) _rep2(i, 0, n)
#define _rep2(i, a, b) for(LOOPVAR_TYPE i = (LOOPVAR_TYPE)(a); i < (LOOPVAR_TYPE)(b); i++)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
 
#define fir first
#define sec second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
 
const double EPS = 1e-9;
const double PI = acos(-1.0);
const long INF = 1070000000LL;
const long MOD = 1000000007LL;
 
using namespace std;
 
typedef istringstream iss;
typedef stringstream sst;
typedef pair<LOOPVAR_TYPE, LOOPVAR_TYPE> pi;
typedef vector<LOOPVAR_TYPE> vi;
  • #define long long long なるほど (long double使う時は邪魔になる?)
  • repマクロが可変長引数で引数の個数によって変わる

amylase

#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
 
using namespace std;
typedef long long li;
typedef long double real;
 
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
  • li派

climpet

#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>
 
#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
 
#define cauto const auto&
#define ALL(v) begin(v),end(v)
#else
#define ALL(v) (v).begin(),(v).end()
#endif
 
using namespace std;
 
 
namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
 
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
 
#define VV(T) vector<vector< T > >
 
template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}
 
template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}
 
 
#define REP(i,n) for(int i=0;i<int(n);++i)
#define RALL(v) (v).rbegin(),(v).rend()
 
 
#define MOD 1000000007LL
#define EPS 1e-8
  • cauto よく使うし欲しい
  • LL派

tanakh

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
  • なし

ここからはジャッジのみ見れるコードなのでリンクなし。

asi1024

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
 
using namespace std;
 
typedef long long ll;
  • ll派

natsugiri

#include<cassert>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
 
typedef long long LL;
typedef vector<int> VI;
 
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)
 
template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
 
  • LL派
  • amin, amax
  • REPの第二引数を変数に代入
  • eprintf

cos65535

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>
 
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
 
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))
  • ll派
  • memset 第一引数と第三引数は大抵こうなるのでこのマクロは欲しいかも

sune2

#include <bits/stdc++.h>
 
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REPR(i,n) for (int i=(int)(n)-1;i>=0;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
typedef long long ll;
typedef pair<int,int> pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os,
const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}
  • chmin, chmax
  • #define tpl(...) make_tuple(__VA_ARGS__) おもしろい
  • 入出力用の関数

ir5

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <sstream>
#include <set>
using namespace std;
using ll = long long;
 
class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};
 
  • ll派
  • rangeクラス

chir

#include <iostream>
#include <bitset>
using namespace std;
 
typedef long long ll;
  • ll派

ichyo

// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;
 
#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif
 
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }
 
void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

テンプレート観察メモ(Codeforces)

Codeforces上位50名のテンプレート、C++のみ、敬称略、まとめはこちら

tourist

#include <bits/stdc++.h>

using namespace std;
  • テンプレートなし

TooSimple

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head
  • rep, それを逆順にしたper
  • all
  • push_back, make_pair -> pb, mp
  • first, second -> fi, se
  • powmodがテンプレートにある
  • vector, long long, pairをtypedef

rng_58

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
  • REP
  • snuke

subscriber

#include<stdio.h>
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<memory.h>
#include<map>
#include<set>
#include<queue>
#include<list>
#include<sstream>
#include<cstring>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define SS stringstream
#define sqr(x) ((x)*(x))
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))
#define CC(x) cout << (x) << endl
#define pw(x) (1ll<<(x))
#define buli(x) __builtin_popcountll(x)
#define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
  • first, second -> F, S
  • memset0埋めマクロ
  • forn: いわゆるrepマクロ
  • CC(x) で出力, デバッグ用?

Petr

#include <vector>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;
  • long long -> ll

vepifanov

#include <cstdio>
#include <numeric>
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <queue>
#include <sstream>
#include <deque>
#include <cassert>

using namespace std;

#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i = 0; i < (n); i++)
#define re return
#define fi first
#define se second
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define sqr(x) ((x) * (x))
#define sqrt(x) sqrt(abs(x))
#define y0 y3487465
#define y1 y8687969
#define fill(x,y) memset(x,y,sizeof(x))
#define prev PREV
#define j0 j1347829
#define j1 j234892

typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef double D;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef vector<vi> vvi;

template<class T> T abs(T x) { re x > 0 ? x : -x; }
  • return -> re 普通にコード内でも使われている
  • size()がunsignedなのをマクロ内でキャスト
  • sqrt(x) 引数を0以上に
  • y0, y1, j0, j1,prevを標準ライブラリ関数名などと被せないように
  • 各種typedef

Um_nik

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;
#define mp make_pair
  • typedef
  • make_pair -> mp

Endagorion

#include <iostream>
#include <tuple>
#include <sstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
  • forn, for1, ford, fore ループのマクロ fornとfordが順番逆、for1は右端含む、foreは区間
  • uin, umax -> updateminの略?更新が起きた時に限りtrue
  • all, rall
  • 各種typedef

WJMZBMR

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

const int MOD = int(1e9) + 7;
typedef long long int64;
  • MOD
  • long long -> int64

mnbvmar

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template<typename TH>
void debug_vars(const char* data, TH head){
    cerr << data << "=" << head << "\n";
}

template<typename TH, typename... TA>
void debug_vars(const char* data, TH head, TA... tail){
    while(*data != ',') cerr << *data++;
    cerr << "=" << head << ",";
    debug_vars(data+1, tail...);
}

#ifdef LOCAL
#define debug(...) debug_vars(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#endif

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).begin())
  • デバッグ用のマクロが可変長引数
  • size()がunsignedなのでintにキャスト

scott_wu

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>

using namespace std;
typedef long long ll;
  • ほぼなし

Egor

#include<cstdio>
#include<cmath>
#include<iostream>

using namespace std;
  • ほぼなし

Merkurev

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#ifdef LOCAL
   #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
   #define eprintf(...) 42
#endif

typedef long long int int64;

qwerty787788

#include <bits/stdc++.h>

using namespace std;
  • なし

ecnerwal

#include<bits/stdc++.h>
using namespace std;

typedef double ld;
  • double -> ld

niyaznigmatul

#include <cstdio>
  • なし

yeputons

#include <iostream>
#include <cstring>
using namespace std;
  • なし

PavelKunyavskiy

//#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <bitset>
#define mp make_pair
#define pb push_back

#ifdef LOCAL
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#else
#define eprintf(...)
#endif

#define TIMESTAMP(x) eprintf("["#x"] Time : %.3lf s.\n", clock()*1.0/CLOCKS_PER_SEC)
#define TIMESTAMPf(x,...) eprintf("[" x "] Time : %.3lf s.\n", __VA_ARGS__, clock()*1.0/CLOCKS_PER_SEC)

#if ( ( _WIN32 || __WIN32__ ) && __cplusplus < 201103L)
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

using namespace std;

#define TASKNAME "E"

#ifdef LOCAL
static struct __timestamper {
    string what;
    __timestamper(const char* what) : what(what){};
    __timestamper(const string& what) : what(what){};
    ~__timestamper(){
        TIMESTAMPf("%s", what.data());
    }
} __TIMESTAMPER("end");
#else 
struct __timestamper {};
#endif

typedef long long ll;
typedef long double ld;
  • aa

al13n

#define _CRT_SECURE_NO_DEPRECATE
#define _USE_MATH_DEFINES
#include <array>
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <ctime>
#include <numeric>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <complex>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <string>
#include <sstream>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef double ld;
typedef pair<int, int> pii;
typedef pair<short, short> pss;
typedef pair<LL, LL> pll;
typedef pair<ULL, ULL> puu;
typedef pair<ld, ld> pdd;
template<class T> inline T sqr(T x) { return x * x; }
template<class T> inline string tostr(const T & x) { stringstream ss; ss << x; return ss.str(); }
inline LL parse(const string & s) { stringstream ss(s); LL x; ss >> x; return x; }
#define left asdleft
#define right asdright
#define link asdlink
#define unlink asdunlink
#define next asdnext
#define prev asdprev
#define y0 asdy0
#define y1 asdy1
#define mp make_pair
#define MT make_tuple
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(ar,val) memset(ar, val, sizeof(ar))
#define istr stringstream
#define forn(i,n) for(int i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define X first
#define Y second
const ld EPS = 1e-12;
const int INF = 1000*1000*1000;
const LL LINF = INF * 1ll * INF;
const ld DINF = 1e200;
const ld PI = 3.1415926535897932384626433832795l;
int gcd(int a,int b){return a?gcd(b%a,a):b;}
LL gcd(LL a,LL b){return a?gcd(b%a,a):b;}
LL powmod(LL a,LL p,LL m){LL r=1;while(p){if(p&1)r=r*a%m;p>>=1;a=a*a%m;}return r;}
bool isprime(LL a){if(a<=1)return false;for (LL i=2;i*i<=a;++i){if(a%i==0)return false;}return true;}
LL sqrtup(LL a){if(!a)return 0;LL x=max(0ll,(LL)sqrt((ld)a));while(x*x>=a)--x;while((x+1)*(x+1)<a)++x;return x+1;}
LL sqrtdown(LL a){LL x=max(0ll,(LL)sqrt((ld)a));while(x*x>a)--x;while((x+1)*(x+1)<=a)++x;return x;}
template<class T> ostream& operator<<(ostream &s, const vector<T> &v);
template<class A,class B> ostream& operator<<(ostream &s, const pair<A,B> &p);
template<class K,class V> ostream& operator<<(ostream &s, const map<K,V> &m);
template<class T,size_t N> ostream& operator<<(ostream &s, const array<T,N> &a);
template<class T> ostream& operator<<(ostream &s, const vector<T> &v){s<<'[';forv(i,v){if(i)s<<',';s<<v[i];}s<<']';return s;}
template<class A,class B> ostream& operator<<(ostream &s, const pair<A,B> &p){s<<"("<<p.X<<","<<p.Y<<")";return s;}
template<class K,class V> ostream& operator<<(ostream &s, const map<K,V> &m){s<<"{";bool f=false;for(const auto &it:m){if(f)s<<",";f=true;s<<it.X<<": "<<it.Y;}s<<"}";return s;}
template<class T,size_t N> ostream& operator<<(ostream &s, const array<T,N> &a){s<<'[';forv(i,a){if(i)s<<',';s<<a[i];}s<<']';return s;}
template<size_t n,class... T> struct put1 { static ostream& put(ostream &s, const tuple<T...> &t){s<<get<sizeof...(T)-n>(t);if(n>1)s<<',';return put1<n-1,T...>::put(s,t);} };
template<class... T> struct put1<0,T...> { static ostream& put(ostream &s, const tuple<T...> &t){return s;} };
template<class... T> ostream& operator<<(ostream &s, const tuple<T...> &t){s<<"(";put1<sizeof...(T),T...>::put(s,t);s<<")";return s;}
ostream& put2(ostream &s, const tuple<> &t){return s;}
template<class U> ostream& put2(ostream &s, const tuple<U> &t){return s<<get<0>(t);}
template<class U,class V,class... T> ostream& put2(ostream &s, const tuple<U,V,T...> &t){return s<<t;}
#ifdef __ASD__
#define dbg(...) do { cerr << #__VA_ARGS__ << " = "; put2(cerr, make_tuple(__VA_ARGS__)); cerr << endl; }while(false)
#else
#define dbg(...) do{}while(false)
#endif
  • 一番上はscanf等の警告抑制?GNU g++で効果あるかは不明
  • 二番目はM_PI使う用

izrak

#include <bits/stdc++.h>

#define FO(i,a,b) for (int i = (a); i < (b); i++)
#define sz(v) int(v.size())

using namespace std;
  • FO: ループ
  • size()をintにキャスト

jcvb

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
using namespace std;
typedef long long ll;
typedef double db;
const db pi=acos(-1);
void gn(int &x){
    int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')sg=-1,x=0;else x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';
    x*=sg;
}
void gn(ll &x){
    int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')sg=-1,x=0;else x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';
    x*=sg;
}
const int mo=1000000007;
const int inf=1061109567;
//const ll inf=1000000000000000000ll;
int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
#define x1 x192837465
#define x2 x123456789
#define y1 y192837465
#define y2 y123456789
using namespace std;
  • 自前の入力関数
  • qp: 累乗の高速計算、MODありなしどっちも
  • gcd
  • dx, dy
  • x1, y1が被らないように

dreamoon

#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
  • size()をintにキャスト
  • all
  • rep, repp
  • 入力がマクロ
  • 変数宣言して入力するマクロ

Kostroma

#pragma comment (linker, "/STACK:1280000000")
#define _CRT_SECURE_NO_WARNINGS
//#include "testlib.h"
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <complex>
using namespace std;
//#define FILENAME ""
#define mp make_pair
#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve();
void precalc();
clock_t start;
//int timer = 1;

int testNumber = 1;

bool todo = true;

int main() {
#ifdef room111
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#else
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //freopen(FILENAME".in", "r", stdin);
    //freopen(FILENAME ".out", "w", stdout);
#endif
    start = clock();
    int t = 1;
    cout.sync_with_stdio(0);
    cin.tie(0);
    precalc();
    cout.precision(10);
    cout << fixed;
    //cin >> t;
    int testNum = 1;
    while (t--) {
        //cout << "Case #" << testNum++ << ": ";
        solve();
        ++testNumber;
        //++timer;
    }

#ifdef room111
    cerr << "\n\n" << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";
#endif

    return 0;
}

//BE CAREFUL: IS INT REALLY INT?

//#define int li

/*int pr[] = { 97, 2011 };
int mods[] = { 1000000007, 1000000009 };

const int C = 300500;
int powers[2][C];*/

//int MOD = 1000000007;

//int c[5010][5010];

//int catalan[200500];

//ld doubleC[100][100];

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

/*int curMod = 1000000009;

int fact[100500], revfact[100500];

int getC(int n, int k) {
int res = fact[n] * revfact[n - k] % curMod * revfact[k] % curMod;
return res;
}*/

//const int C = 500500;

//int least_prime[C];

void precalc() {

    /*for (int i = 2; i < C; ++i) {
       if (!least_prime[i]) {
           least_prime[i] = i;
           for (li j = i * 1LL * i; j < C; j += i) {
               least_prime[j] = i;
           }
       }
   }*/

    /*fact[0] = revfact[0] = 1;
   for (int i = 1; i < 100500; ++i) {
   fact[i] = fact[i - 1] * i % curMod;
   revfact[i] = binpow(fact[i], curMod - 2, curMod);
   }*/

    /*for (int w = 0; w < 2; ++w) {
   powers[w][0] = 1;
   for (int j = 1; j < C; ++j) {
   powers[w][j] = (powers[w][j - 1] * 1LL * pr[w]) % mods[w];
   }
   }*/

    /*catalan[0] = 1;
   for (int n = 0; n < 200500 - 1; ++n) {
   catalan[n + 1] = catalan[n] * 2 * (2 * n + 1) % MOD * binpow(n + 2, MOD - 2, MOD) % MOD;
   }*/

    /*for (int i = 0; i < 5010; ++i) {
   c[i][i] = c[i][0] = 1;
   for (int j = 1; j < i; ++j) {
   c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
   }
   }*/

    /*for (int i = 0; i < 100; ++i) {
   doubleC[i][i] = doubleC[i][0] = 1.0;
   for (int j = 1; j < i; ++j) {
   doubleC[i][j] = doubleC[i - 1][j - 1] + doubleC[i - 1][j];
   }
   }*/

}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}


//#define int li

//const int mod = 1000000007;

typedef double ldd;

#define double ld
  • 一番上の行はスタックを拡張するおまじないだが、MSVC++でしか意味が無い
  • 二行目はこれまたMSVC++にしか関係なくて、scanf等のバッファオーバーランが発生する可能性のある関数を使った時の警告を抑制するらしい
  • precalcの中に素数篩、階乗とあるmodでのその逆元、カタラン数、二項係数などがあり、コメントアウトすることで使えるようになってる
  • gcd, lcm

Marcin_smu

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
typedef double D;
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define R(I,N) for(int I=0;I<N;I++)
#define F(I,A,B) for(int I=A;I<B;I++)
#define FD(I,N) for(int I=N-1;I>=0;I--)
#define make(A) scanf("%d",&A)
#define make2(A,B) scanf("%d%d",&A,&B)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
template<typename C> void maxi(C& a,C b){if(a<b)a=b;}
template<typename C> void mini(C& a,C b){if(a>b)a=b;}

template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a){
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...);
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(C) {for(auto&c:C)cerr<<c<<",";cerr<<endl;}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(C) {}
#define cerr if(0)cout
#endif

overtroll

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <queue>
#include <stack>
#include <bitset>
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define mt make_tuple
#define NAME ""

using namespace std;

typedef long long ll;
typedef long double ld;

const ld PI = acos(-1.0);
  • first, second -> fs, sc
  • make_tuple -> mt

RAD

#define _CRT_SECURE_NO_DEPRECATE
#define _SECURE_SCL 0

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>
#include <iostream>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <cctype>
#include <sstream>
#include <cassert>
#include <bitset>
#include <memory.h>
#include <complex>
#include <iomanip>

using namespace std;

#pragma comment(linker, "/STACK:200000000")

typedef long long int64;

#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
#define fore(i, a, n) for(int i = (int)(a); i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define last(a) (int(a.size()) - 1)
#define all(a) a.begin(), a.end()

const double EPS = 1E-9;
const int INF = 1000000000;
const int64 INF64 = (int64) 1E18;
const double PI = 3.1415926535897932384626433832795;

const int CMAX = 1100000;
const int64 MOD = INF + 7;
  • 一番上はscanf等の警告抑制?GNU g++で効果あるかは不明
  • last: 最後のインデックス

TankEngineer

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
  • なし

Swistakk

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define st first
#define nd second
#define rd third
#define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
#define RE(i, n) FOR(i, 1, n)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define REP(i, n) for(int i = 0;i <(n); ++i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define cerr if(0)cout
#endif
#define make(type, x) type x; cin>>x;
#define make2(type, x, y) type x, y; cin>>x>>y;
#define make3(type, x, y, z) type x, y, z; cin>>x>>y>>z;
#define make4(type, x, y, z, t) type x, y, z, t; cin>>x>>y>>z>>t;
#define next ____next
#define prev ____prev
#define left ____left
#define hash ____hash
typedef long long ll;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<pair<int, int> > VPII;
typedef vector<pair<ll, ll> > VPLL;

template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
template<class T1, class T2>
ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
template<class A, class B, class C> struct Triple { A first; B second; C third;
  bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
template<class T> void ResizeVec(T&, vector<int>) {}
template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  for (T& v : vec) { ResizeVec(v, sz); }
}
typedef Triple<int, int, int> TIII;
template<class A, class B, class C>
ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }

typedef pair<int, bool> PIB;
  • next, prev, left, hash

anta

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
  • aut
  • amin, amax
  • rep, rer, reu

sdya

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <stack>
#include <ctime>
#include <unordered_map>
#include <unordered_set>
#pragma comment (linker, "/STACK:256000000")

using namespace std;

bmerry

#include <bits/stdc++.h>

/*** TEMPLATE CODE STARTS HERE ***/

using namespace std;

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef complex<double> pnt;
typedef pair<int, int> pii;

#define RA(x) begin(x), end(x)
#define FE(i, x) for (auto i = begin(x); i != end(x); ++i)
#define SZ(x) ((int) (x).size())

template<class T>
void splitstr(const string &s, vector<T> &out)
{
    istringstream in(s);
    out.clear();
    copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

static void redirect(int argc, const char **argv)
{
    ios::sync_with_stdio(false);
    if (argc > 1)
    {
        static filebuf f;
        f.open(argv[1], ios::in);
        cin.rdbuf(&f);
        if (!cin)
        {
            cerr << "Failed to open '" << argv[1] << "'" << endl;
            exit(1);
        }
    }

    if (argc > 2)
    {
        static filebuf f;
        f.open(argv[2], ios::out | ios::trunc);
        cout.rdbuf(&f);
        if (!cout)
        {
            cerr << "Failed to open '" << argv[2] << "'" << endl;
        }
    }
}

/*** TEMPLATE CODE ENDS HERE */
  • redirect: main関数の最初に呼び出してリダイレクトする

TeaPot

#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include <cstring>
#include <cassert>
#include <bitset>
#include <sstream>
#include <queue>

#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define sz(a) ((int) (a).size())
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long int64;
typedef long double ldb;

const long double eps = 1e-9;
const int inf = (1 << 30) - 1;
const long long inf64 = ((long long)1 << 62) - 1;
const long double pi = acos(-1);

template <class T> T sqr (T x) {return x * x;}
template <class T> T abs (T x) {return x < 0 ? -x : x;}
  • eprintf
  • sqr, abs

Shik

// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) do { \
    fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
    _dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0);

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif

template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }

void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
    _R(head);
    R(tail...);
}

template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
    for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
        if ( i!=x.cbegin() ) putchar(' ');
        _W(*i);
    }
}

void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
    _W(head);
    putchar(sizeof...(tail)?' ':'\n');
    W(tail...);
}

// }}}
  • 入出力

Golovanov399

#include <bits/stdc++.h>

#define itn int
#define LL long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define all(x) (x).begin(), (x).end()

using namespace std;

inline int nxt(){
    int x;
    scanf("%d", &x);
    return x;
}
  • nxt
  • #define itn int おもしろい

izban

#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cassert>
#include <ctime>
#include <map>
#include <math.h>
#include <cstdio>
#include <set>
#include <deque>
#include <memory.h>
#include <queue>

#pragma comment(linker, "/STACK:64000000")
typedef long long ll;

using namespace std;

const int MAXN = -1;
const int MOD = 1; // 1000 * 1000 * 1000 + 7;
  • なし

kcm1700

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <climits>
#include <cstdint>
#include <string>
#include <cstring>

using namespace std;
  • なし

enot.1.10

/**
 *    author:  enot.1.10, (concealed)
 *    created: 19.12.2015 13:55:16
**/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <ctime>
#include <cassert>
#include <queue>

#define fs first
#define sc second
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
#define forit(it,v) for(typeof((v).begin()) it = v.begin() ; it != (v).end() ; ++it)
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),a.end()
#define pw(x) (1LL<<(x))

using namespace std;

typedef long long ll;
typedef double dbl;
typedef vector<int> vi;
typedef pair<int, int> pi;

const int inf = (int)1.01e9;
const dbl eps = 1e-9;

/* --- main part --- */
  • 本名日時が入るようになってる
  • eprintf 可変長引数のデバッグ出力用マクロ

Belonogov

#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <bitset>

using namespace std;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define epr(...) fprintf(stderr, __VA_ARGS__)
#define db(x) cerr << #x << " = " << x << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n"; 
#define all(a) (a).begin(), (a).end()

#define equal equalll
#define less lesss
const int N = -1;
const long long INF = 1e9 + 19;
typedef unsigned long long ull;
  • equal, lessが被らないように
  • このデバッグ出力結構見るなぁ

-XraY-

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <cassert>
#include <ctime>
#include <string>
#include <queue>

using namespace std;

#ifdef _WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif

typedef long double ld;

long long rdtsc() {
  long long tmp;
  asm("rdtsc" : "=A"(tmp));
  return tmp;
}

inline int myrand() {
  return abs((rand() << 15) ^ rand());
}

inline int rnd(int x) {
  return myrand() % x;
}

#define pb push_back
#define mp make_pair
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define sz(x) ((int)(x).size())
#define TASKNAME "text"

const int INF = (int) 1.01e9;
const ld EPS = 1e-9;

mR.ilchi

#include <bits/stdc++.h>
using namespace std;
  • なし

hogloid

#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifndef ONLINE_JUDGE
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }
typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

lint readL(){
  lint res;
#ifdef ONLINE_JUDGE
  scanf("%I64d",&res);
#else
  scanf("%lld",&res);
#endif
  return res;
}
void printL(lint res){
#ifdef ONLINE_JUDGE
  printf("%I64d",res);
#else
  printf("%lld",res);
#endif
}
  • CFは%lldが入ってると警告が出るけど無視しても問題ないらしい(警告を二度と表示しないというチェックボックスがあるので選択)

wjh720

#include <bits/stdc++.h>
#define fi first
#define se second
#define PA pair<int,int>
#define VI vector<int>
#define VP vector<PA >
#define mk(x,y) make_pair(x,y)
#define int64 long long
#define db double
#define N 300010
#define P 100000000001101ll
#define wei 31
#define For(i,x,y) for (i=x;i<=y;i++)
using namespace std;
  • int64

RomaWhite

#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <cassert>
#include<complex>
#include <time.h>
using namespace std;

#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
#define FILL(A,value) memset(A,value,sizeof(A))

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
#define x0 ikjnrmthklmnt
#define y0 lkrjhkltr
#define y1 ewrgrg

typedef long long Int;
typedef unsigned long long UInt;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef complex<double> base;
  • Int派

step4

#include<bits/stdc++.h>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define FZ(n) memset((n),0,sizeof(n))
#define FMO(n) memset((n),-1,sizeof(n))
#define MC(n,m) memcpy((n),(m),sizeof(n))
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define FOR(x,y) for(__typeof(y.begin())x=y.begin();x!=y.end();x++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
// Let's Fight!
  • IOS; でcin高速化()

Zlobober

#include <cstdio>
#include <cassert>
#include <memory.h>
#include <iostream>
#include <tuple>
using namespace std;

typedef long long llong;
  • llong派

W4yneb0t

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
  • in派

ershov.stanislav

#include <bits/stdc++.h>

#define mp make_pair
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back

#define all(s) (s).begin(), (s).end()
#define sz(s) ((int) ((s).size()))

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
const ll lINF = 1e18;
const double EPS = 1e-12;

#ifdef _WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif

using namespace std;
  • ll派
  • CF環境では_WIN32が定義されている

ilyakor

#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <cmath>
#include <cassert>
#include <queue>
#include <bitset>
#include <map>
#include <set>

#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()

using namespace std;

typedef long long int64;
typedef pair<int, int> ii;
typedef vector<int> vi;
  • int64派

AOJ 1334 Cubic Colonies

これはAOJ-ICPC Advent Calendar 2015の2日目の記事です。

AOJ自体長らく触っていませんが、自分が解いたことのある問題の中で「AOJ (問題番号)」でぐぐっても解説記事が出てこない問題がないか探して、この問題について書くことにしました。

問題: Cubic Colonies | Aizu Online Judge

2012年のICPC地区予選の最終防衛問題で、本番中に解かれた問題です。
複数の立方体からなる物体があり、物体の表面にはケーブルを敷くことができます。物体の表面上の2点が与えられるので、その間を結ぶ長さ最小のケーブルを求めて下さい。
内容把握したと思いつつ問題文の下にある図が目に入ると「そんなところも通れるんかーい!」とツッコまずにはいられません。
物理的に可能かどうかはさておき、表面であれば自由にケーブルを敷けるということで、表面に頂点と辺を追加して最短経路問題にして解けます。

解法

どこに面があるか調べる

隣り合ったマスの片方のみに物体があれば面ができます。

面に頂点と辺を加える

ケーブルがどのように敷かれるか展開図で考えてみると、2つの格子点間を結ぶ線分の組み合わせになることが分かります。サイズも 3\times 3\times 3と小さいので、一つの線分もせいぜい 10 \times 10程度に収まりそうです。で、ひとつの面だけ取り出してみると、長さ1の線分を[0,1]とみなして0,1,{n/m; 0 < n < m <= D}に頂点を置く、というのを全ての辺についてやって、異なる辺にある2つの頂点間に辺を張ればよいです。分母の最大値をDと置いてますが、そんなに大きくなりそうにないのでコード内ではとりあえず9にしています。

単一始点最短路を解く

スタートに対応する頂点からゴールに対応する頂点までの最短路を計算します。
面の数は108、頂点の数は粗く見積もって 12\times 4\times 3 \times D^2個未満、辺の数は粗く見積もって 108\times 3 \times D^4個未満、ダイクストラ法で間に合います。(一つのインプットが複数データセットからなるなら、ちゃんとその数も書いてあるといいのになぁ)

2年前にAOJに提出したコードではダイクストラをしてました。(295ms)

今年向けに書き直すついでに高速化しようと思ったのですが、バグが取れませんでした。日付が変わる前に一旦投稿します・・・

感想

やることを挙げると大した事はないですが、実装量は意外とあって、その割にはライブラリで殴る問題でもない不思議な問題でした。デバッグがつらい。

コード

2年前のクソコード

#include <bits/stdc++.h>
#define iter(i,s,n) for(int i=int(s);i<int(n);i++)
#define rep(i,n) iter(i,0,n)
#define all(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;
template<class T>void chmin(T &t, T f){if(t > f)t = f;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}

vector<double> frac;

struct edge{int to;double cost;};
struct edgeid{int x,y,z,d;};
vector<edge> G[8000];

int edge_id(int x,int y,int z,int d){return ((x*4+y)*4+z)*3+d;}
int edge_ide(edgeid e){return edge_id(e.x,e.y,e.z,e.d);}
int node_id(int x,int y,int z, int d,int f){return edge_id(x,y,z,d)*frac.size()+f;}
int node_ide(edgeid e, int f){return node_id(e.x,e.y,e.z,e.d,f);}

struct node{double x,y,z;};
node no[8000];
void print_node(node a){printf("%f %f %f\n",a.x,a.y,a.z);}
void print(int id){print_node(no[id]);}

double d[8000];

void connect(int x,int y,int z,int d){
    int S = frac.size();
    int added = 0;
    //printf("<%d %d %d %c>\n",x,y,z,d+'x');
    //x
    //e[x,y,z,2], e[x,y,z,3], e[x,y+1,z,2], e[x,y,z+1,3]
    vector<edgeid> f;
    if(d==0){
        //printf("<%d %d %d x>\n",x,y,z);
        f.push_back({x,y,z,1});
        f.push_back({x,y,z,2});
        f.push_back({x,y,z+1,1});
        f.push_back({x,y+1,z,2});
    }
    //y
    if(d==1){
        //printf("<%d %d %d y>\n",x,y,z);
        f.push_back({x,y,z,0});
        f.push_back({x,y,z,2});
        f.push_back({x,y,z+1,0});
        f.push_back({x+1,y,z,2});
    }
    //z
    if(d==2){
        //printf("<%d %d %d z>\n",x,y,z);
        f.push_back({x,y,z,0});
        f.push_back({x,y,z,1});
        f.push_back({x,y+1,z,0});
        f.push_back({x+1,y,z,1});
    }

    //mukaiau
    rep(i1,2){
        //printf("[[%s++]]\n",d==1?i1?"z":"y":d==2?i1?"z":"x":i1?"y":"x");
        rep(j1,S){
            int s = node_ide(f[i1],j1);
            rep(j2,S){
                int t = node_ide(f[i1+2],j2);
                double d = hypot(1.0,frac[j1]-frac[j2]);
                G[s].push_back({t,d}); G[t].push_back({s,d});
                //print(s); print(t); printf("%f\n",d);
                added++;
            }
        }
    }

    //tonariau
    rep(j1,S){
        int s = node_ide(f[0],j1);
        rep(j2,S){
            int t = node_ide(f[1],j2);
            double d = hypot(frac[j1],frac[j2]);
            G[s].push_back({t,d}); G[t].push_back({s,d});
            added++;
        }
    }

    rep(j1,S){
        int s = node_ide(f[0],j1);
        rep(j2,S){
            int t = node_ide(f[3],j2);
            double d = hypot(1-frac[j1],frac[j2]);
            G[s].push_back({t,d}); G[t].push_back({s,d});
            added++;
        }
    }

    rep(j1,S){
        int s = node_ide(f[1],j1);
        rep(j2,S){
            int t = node_ide(f[2],j2);
            double d = hypot(1-frac[j1],frac[j2]);
            G[s].push_back({t,d}); G[t].push_back({s,d});
        }
    }

    rep(j1,S){
        int s = node_ide(f[2],j1);
        rep(j2,S){
            int t = node_ide(f[3],j2);
            double d = hypot(1-frac[j1],1-frac[j2]);
            G[s].push_back({t,d}); G[t].push_back({s,d});
        }
    }

    //cout << added << endl;
}

int main(){
    //init
    for(int i=2; i<=9; i++){
        for(int j=1; j<i; j++){
            if(gcd(i,j) > 1) continue;
            frac.push_back((double)j/i);
        }
    }
    frac.push_back(0); frac.push_back(1);
    sort(all(frac));

    //cout << frac.size() << endl;

    rep(x,4) rep(y,4) rep(z,4) rep(f,frac.size()){
        //printf("%d %d %d\n",node_id(x,y,z,0,f),node_id(x,y,z,1,f),node_id(x,y,z,2,f));
        no[node_id(x,y,z,0,f)] = {x+frac[f],(double)y,(double)z};
        no[node_id(x,y,z,1,f)] = {(double)x,y+frac[f],(double)z};
        no[node_id(x,y,z,2,f)] = {(double)x,(double)y,z+frac[f]};
    }
    //repl
    int sx,sy,sz,tx,ty,tz;
    while(cin >> sx >> sy >> sz >> tx >> ty >> tz, sx|sy|sz|tx|ty|tz){
        char bl[5][5][5];
        memset(bl,'.',sizeof(bl));
        iter(z,1,4) iter(y,1,4) iter(x,1,4){
            int c = getchar();
            while(c == 32 || c == 10) c = getchar();
            bl[x][y][z] = c;
        }

        //rep(i,5){
        //    rep(j,5){
        //        rep(k,5) putchar(bl[i][j][k]);
        //        puts("");
        //    }
        //    puts("------------");
        //}

        //edge_init
        rep(i,8000) G[i].clear();

        rep(x,4) rep(y,4) rep(z,4){
            vector<int> same;
            same.push_back(node_id(x,y,z,0,0));
            same.push_back(node_id(x,y,z,1,0));
            same.push_back(node_id(x,y,z,2,0));
            if(x>0) same.push_back(node_id(x-1,y,z,0,frac.size()-1));
            if(y>0) same.push_back(node_id(x,y-1,z,1,frac.size()-1));
            if(z>0) same.push_back(node_id(x,y,z-1,2,frac.size()-1));
            rep(i,same.size()) rep(j,same.size()){
                if(i==j) continue;
                G[same[i]].push_back({same[j],0.0});
            }
            //G[node_id(x,y,z,0,0)].push_back({node_id(x,y,z,0,frac.size()-1),1.0});
            //G[node_id(x,y,z,1,0)].push_back({node_id(x,y,z,1,frac.size()-1),1.0});
            //G[node_id(x,y,z,2,0)].push_back({node_id(x,y,z,2,frac.size()-1),1.0});
        }

        rep(x,4) rep(y,4) rep(z,4){
            if(bl[x+1][y][z] != bl[x][y][z]) connect(x,y-1,z-1,0);
            if(bl[x][y+1][z] != bl[x][y][z]) connect(x-1,y,z-1,1);
            if(bl[x][y][z+1] != bl[x][y][z]) connect(x-1,y-1,z,2);
        }

        //dist init
        rep(i,8000) d[i] = 1e9;
        d[node_id(sx,sy,sz,0,0)] = 0;
        //G[node_id(sx+1,sy+1,sz+1,0,0)].push_back({node_id(sx+1,sy+1,sz+1,1,0),0.0});
        priority_queue<pair<double,int>, vector<pair<double,int>>,greater<pair<double,int>>> pq;
        pq.push({0.0, node_id(sx,sy,sz,0,0)});
        int goal = node_id(tx,ty,tz,0,0);
        int zz = 0;
        while(!pq.empty()){
            zz++;
            //printf("[%d]",zz);
            auto p = pq.top(); pq.pop();
            int v = p.second;
            if(d[v] < p.first) continue;

            if(v == goal){
                cout << fixed << setprecision(12) << d[goal] << endl;
                break;
            }

            //printf("((%d))",G[v].size());
            rep(i,G[v].size()){
                edge e = G[v][i];
                if(d[e.to] > d[v] + e.cost){
                    d[e.to] = d[v] + e.cost;
                    pq.emplace(d[e.to],e.to);
                }
            }
        }

        //cout << fixed << setprecision(12) << d[goal] << endl;
    }
}