SHOW:
|
|
- or go back to the newest paste.
| 1 | #define fileName string ("")
| |
| 2 | ||
| 3 | //#define TEST_GENERATOR | |
| 4 | ||
| 5 | #define INP (fileName + ".inp").c_str () | |
| 6 | #define OUT (fileName + ".out").c_str () | |
| 7 | #define ERR (fileName + ".err").c_str () | |
| 8 | ||
| 9 | /* ---------------------------------------------------------------------------------------- */ | |
| 10 | ||
| 11 | #include <algorithm> | |
| 12 | #include <iostream> | |
| 13 | #include <sstream> | |
| 14 | #include <cstdlib> | |
| 15 | #include <climits> | |
| 16 | #include <cstring> | |
| 17 | #include <iomanip> | |
| 18 | #include <limits> | |
| 19 | #include <locale> | |
| 20 | #include <cstdio> | |
| 21 | #include <vector> | |
| 22 | #include <cmath> | |
| 23 | #include <stack> | |
| 24 | #include <queue> | |
| 25 | #include <deque> | |
| 26 | #include <ctime> | |
| 27 | #include <map> | |
| 28 | #include <set> | |
| 29 | ||
| 30 | using namespace std; | |
| 31 | ||
| 32 | #define fi first | |
| 33 | #define se second | |
| 34 | #define mp make_pair | |
| 35 | #define pb push_back | |
| 36 | ||
| 37 | #define rp(i, n) for (int i = 0; i < (n); ++i) | |
| 38 | #define rd(i, n) for (int i = (n); i--;) | |
| 39 | #define rs(i, x) rp (i, sz (x)) | |
| 40 | #define fr(i, a, b) for (int i = (a); i <= (b); ++i) | |
| 41 | #define fd(i, a, b) for (int i = (a); i >= (b); --i) | |
| 42 | #define fe(i, x) for (__typeof ((x).begin ()) i = (x).begin (); i != (x).end (); ++i) | |
| 43 | #define fer(i, x) for (__typeof ((x).rbegin ()) i = (x).rbegin (); i != (x).rend (); ++i) | |
| 44 | #define cd(x) while ((x)--) | |
| 45 | #define nt(n) for (int i = (n); i--;) | |
| 46 | #define srt(v) sort (all (v)) | |
| 47 | ||
| 48 | #define mn(x, y) x = min (x, y) | |
| 49 | #define mx(x, y) x = max (x, y) | |
| 50 | ||
| 51 | #define sz(x) (int) (x).size () | |
| 52 | #define all(x) (x).begin (), (x).end () | |
| 53 | ||
| 54 | #define cl(x) memset (x, 0, sizeof (x)) | |
| 55 | ||
| 56 | #define sqr(x) ((x) * (x)) | |
| 57 | ||
| 58 | const double pi = acos(-1.0); | |
| 59 | ||
| 60 | typedef unsigned long long llu; | |
| 61 | typedef long long ll; | |
| 62 | ||
| 63 | typedef pair <int, int> ii; | |
| 64 | typedef vector <string> vs; | |
| 65 | typedef vector <ii> vii; | |
| 66 | typedef vector <int> vi; | |
| 67 | typedef vector <vi> vvi; | |
| 68 | typedef vector <vii> vvii; | |
| 69 | typedef vector <bool> vb; | |
| 70 | typedef vector <vb> vvb; | |
| 71 | ||
| 72 | template <class T> | |
| 73 | inline string ns (const T &number) | |
| 74 | {
| |
| 75 | stringstream ss; | |
| 76 | ss << number; | |
| 77 | return ss.str (); | |
| 78 | } | |
| 79 | ||
| 80 | template <class T> | |
| 81 | inline T sn (const string &text) | |
| 82 | {
| |
| 83 | stringstream ss (text); | |
| 84 | T result; | |
| 85 | return ss >> result ? result : 0; | |
| 86 | } | |
| 87 | ||
| 88 | template <class T> | |
| 89 | - | T pow2 (const int &x) |
| 89 | + | inline T pow2 (const int &x) |
| 90 | {
| |
| 91 | return (T) 1 << x; | |
| 92 | } | |
| 93 | ||
| 94 | template <class T> | |
| 95 | - | int log2 (T x) |
| 95 | + | inline int log2 (T x) |
| 96 | {
| |
| 97 | int res = 0; | |
| 98 | while (x >>= 1) ++res; | |
| 99 | return res; | |
| 100 | } | |
| 101 | ||
| 102 | struct disjoint_set | |
| 103 | {
| |
| 104 | vi pset; | |
| 105 | int _sz; | |
| 106 | inline int size () {return _sz;}
| |
| 107 | inline void init (const int &n) | |
| 108 | {
| |
| 109 | pset.resize (n); | |
| 110 | rp (i, n) pset [i] = i; | |
| 111 | _sz = n; | |
| 112 | } | |
| 113 | disjoint_set () {};
| |
| 114 | disjoint_set (const int &n) {init (n);}
| |
| 115 | int find (const int &x) {return (x == pset [x] ? x : pset [x] = find (pset [x]));}
| |
| 116 | inline bool same (const int &x, const int &y) {return (find (x) == find (y));}
| |
| 117 | inline bool join (const int &x, const int &y) | |
| 118 | {
| |
| 119 | int xx = find (x), yy = find (y); | |
| 120 | if (xx == yy) return false; | |
| 121 | --_sz; pset [xx] = yy; return true; | |
| 122 | } | |
| 123 | }; | |
| 124 | ||
| 125 | template <class T> | |
| 126 | inline T rand () | |
| 127 | {
| |
| 128 | int cnt = sizeof (T) * 8 / 15 + 1; | |
| 129 | T res = 0; | |
| 130 | cd (cnt) res = (res << 15) + rand (); | |
| 131 | return res; | |
| 132 | } | |
| 133 | ||
| 134 | template <class T> | |
| 135 | inline T rand (T x, T y) | |
| 136 | {
| |
| 137 | if (x > y) swap (x, y); | |
| 138 | T diff = y - x + 1, tmp = rand <T> () % diff; | |
| 139 | if (tmp >= 0) return tmp + x; | |
| 140 | return tmp + diff + x; | |
| 141 | } | |
| 142 | ||
| 143 | /* ---------------------------------------------------------------------------------------- */ | |
| 144 | ||
| 145 | ||
| 146 | ||
| 147 | int main () | |
| 148 | {
| |
| 149 | srand (time (NULL)); | |
| 150 | #ifndef ONLINE_JUDGE | |
| 151 | #ifdef TEST_GENERATOR | |
| 152 | freopen (INP, "w", stdout); | |
| 153 | #else | |
| 154 | freopen (INP, "r", stdin); | |
| 155 | freopen (OUT, "w", stdout); | |
| 156 | //freopen (ERR, "w", stderr); | |
| 157 | #endif | |
| 158 | #endif | |
| 159 | ||
| 160 | return 0; | |
| 161 | } |
