Advertisement
ALENTL

Untitled

Oct 2nd, 2022
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.42 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #pragma GCC optimize("Ofast,unroll-loops")
  5. #pragma GCC target("avx,avx2,fma")
  6.  
  7. #define ll long long
  8. #define ld long double
  9. #define ar array
  10.  
  11. typedef unsigned long long ull;
  12.  
  13. #include <ext/pb_ds/assoc_container.hpp>
  14. #include <ext/pb_ds/tree_policy.hpp>
  15. using namespace __gnu_pbds;
  16.  
  17. template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  18. template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
  19. void dbg_out() { cerr << endl; }
  20. template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
  21. #ifdef LOCAL
  22. #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  23. #else
  24. #define dbg(...)
  25. #endif
  26.  
  27. template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  28.  
  29. #define vt vector
  30. #define pb push_back
  31. #define all(c) (c).begin(), (c).end()
  32. #define sza(x) ((int)x.size())
  33. #define sz(x) (int)(x).size()
  34.  
  35. const int MAX_N = 1e5 + 5;
  36. const double PI = 3.141592653589793238463;
  37. const ll MOD = 1e9 + 7;
  38. const ll INF = 1e9;
  39. const ld EPS = 1e-9;
  40.  
  41. #define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
  42. #define F_OR1(e) F_OR(i, 0, e, 1)
  43. #define F_OR2(i, e) F_OR(i, 0, e, 1)
  44. #define F_OR3(i, b, e) F_OR(i, b, e, 1)
  45. #define F_OR4(i, b, e, s) F_OR(i, b, e, s)
  46. #define GET5(a, b, c, d, e, ...) e
  47. #define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
  48. #define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
  49. #define EACH(x, a) for (auto& x: a)
  50. #define mp make_pair
  51. #define REP(i,n) for (int i = 0; i < n; i++)
  52. #define FORE(i,a,b) for (int i = a; i < b; i++)
  53. #define REPD(i,n) for (int i = n-1; i >= 0; i--)
  54. #define FORD(i,a,b) for (int i = a; i >= b; i--)
  55. #define remax(a,b) a = max(a,b)
  56. #define remin(a,b) a = min(a,b)
  57.  
  58. // RANDOM NUMBER GENERATOR
  59. mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
  60. #define SHUF(v) shuffle(all(v), RNG);
  61.  
  62. // BITWISE
  63. #define BIT_SET(a,b) ((a) |= (1ULL<<(b)))
  64. #define BIT_CLEAR(a,b) ((a) &= ~(1ULL<<(b)))
  65. #define BIT_FLIP(a,b) ((a) ^= (1ULL<<(b)))
  66.  
  67. // '!!' to make sure this returns 0 or 1
  68. #define BIT_CHECK(a,b) (!!((a) & (1ULL<<(b))))
  69.  
  70. #define BITMASK_SET(x, mask) ((x) |= (mask))
  71. #define BITMASK_CLEAR(x, mask) ((x) &= (~(mask)))
  72. #define BITMASK_FLIP(x, mask) ((x) ^= (mask))
  73. #define BITMASK_CHECK_ALL(x, mask) (!(~(x) & (mask)))
  74. #define BITMASK_CHECK_ANY(x, mask) ((x) & (mask))
  75.  
  76.  
  77. /****************** Prime Generator **********************/
  78. const int N=1e7+10; int prime[20000010];
  79. bool isprime[N];
  80. int nprime;
  81.  
  82. template <typename T> void Sieve(T a)
  83. {nprime = 0;memset(isprime,true,sizeof(isprime));
  84. isprime[1]=false;for(int i=2;i<N;i++){
  85. if(isprime[i]){prime[nprime++]=i;for(int j=2;i*j<N;j++)
  86. isprime[i*j]=false;}}}
  87.  
  88. ull mulmod(ull a, ull b, ull c) {
  89. ull x = 0, y=a%c;
  90.  
  91. while(b>0) {
  92. if (b&1)
  93. x = (x+y)%c;
  94. y = (y<<1)%c;
  95. b >>= 1;
  96. }
  97. return x;
  98. }
  99.  
  100. ull pow(ull a, ull b, ull c) {
  101. ull x = 1, y = a;
  102.  
  103. while(b > 0) {
  104. if (b&1) x = mulmod(x,y,c);
  105. y = mulmod(y,y,c);
  106. b >>= 1;
  107. }
  108. return x;
  109. }
  110.  
  111. template <typename T> bool miller_rabin(ull p, int it){
  112. if(p<2) return false;
  113. if(p==2) return true;
  114. if((p&1)==0) return false;
  115.  
  116. ull s = p-1;
  117. while(s%2==0) s >>= 1;
  118.  
  119. while(it--){
  120. ull a = rand()%(p-1)+1,temp = s;
  121. ull mod = pow(a,temp,p);
  122.  
  123. if(mod==-1 || mod==1) continue;
  124.  
  125. while(temp!=p-1 && mod!=p-1){
  126. mod = mulmod(mod,mod,p);
  127. temp <<= 1;
  128. }
  129.  
  130. if(mod!=p-1) return false;
  131. }
  132.  
  133. return true;
  134. }
  135. template <typename T> inline T PrimeFactors(T n)
  136. {ll cnt=0,sum=1;for(int i=0; prime[i]*prime[i]<=n
  137. and i<nprime;i++){cnt=0;while(n%prime[i]==0)
  138. {cnt++;n/=prime[i];}sum*=(cnt+1);}
  139. if(n>1)sum*=2;return sum;}
  140. /****************** Prime Generator End **********************/
  141.  
  142. // ----------------------<MATH>---------------------------
  143.  
  144. template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
  145.  
  146. template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
  147.  
  148. int add(int a, int b, int c = MOD){int res=a+b;
  149. return(res>=c?res-c:res);}
  150. int mod_neg(int a, int b, int c = MOD){int res;
  151. if(abs(a-b)<c)res=a-b;else res=(a-b)%c;
  152. return(res<0?res+c:res);}
  153. int mul(int a, int b, int c = MOD){ll res=(ll)a*b;
  154. return(res>=c?res%c:res);}
  155. int muln(int a, int b, int c = MOD){ll res=(ll)a*b;
  156. return ((res%c)+c)%c;}
  157. ll mulmod(ll a,ll b, ll m = MOD){ll q = (ll)(((ld)a*(ld)b)/(ld)m);
  158. ll r=a*b-q*m;if(r>m)r%=m;if(r<0)r+=m;return r;}
  159. template<typename T>T expo(T e, T n){T x=1,p=e;while(n)
  160. {if(n&1)x=x*p;p=p*p;n>>=1;}return x;}
  161. template<typename T>T power(T e, T n, T m = MOD){T x=1,p=e;while(n)
  162. {if(n&1)x=mul(x,p,m);p=mul(p,p,m);n>>=1;}return x;}
  163. template<typename T>T extended_euclid(T a, T b, T &x, T &y)
  164. {T xx=0,yy=1;y=0;x=1;while(b){T q=a/b,t=b;b=a%b;a=t;t=xx;xx=x-q*xx;x=t;t=yy;yy=y-q*yy;y=t;}return a;}
  165. template<typename T>T mod_inverse(T a, T n = MOD){T x,y,z=0;
  166. T d=extended_euclid(a,n,x,y);return(d>1?-1:mod_neg(x,z,n));}
  167.  
  168.  
  169. template<class T> bool umin(T& a, const T& b) {
  170. return b<a?a=b, 1:0;
  171. }
  172. template<class T> bool umax(T& a, const T& b) {
  173. return a<b?a=b, 1:0;
  174. }
  175.  
  176. ll power(ll a, ll b, ll mod) {
  177. ll x=1, y=a;
  178. while(b>0) {
  179. if (b%2){
  180. x = (x*y)%mod;
  181. }
  182. y = (y*y)%mod;
  183. b/=2;
  184. }
  185. return x%mod;
  186. }
  187.  
  188. ll modular_inverse(ll n, ll mod) {
  189. return power(n, mod-2, mod);
  190. }
  191.  
  192. ll FIRSTTRUE(function<bool(ll)> f, ll lb, ll rb) {
  193. while(lb<rb) {
  194. ll mb=(lb+rb)/2;
  195. f(mb)?rb=mb:lb=mb+1;
  196. }
  197. return lb;
  198. }
  199. ll LASTTRUE(function<bool(ll)> f, ll lb, ll rb) {
  200. while(lb<rb) {
  201. ll mb=(lb+rb+1)/2;
  202. f(mb)?lb=mb:rb=mb-1;
  203. }
  204. return lb;
  205. }
  206.  
  207. const int FACSZ = 1;
  208. int fact[FACSZ], ifact[FACSZ];
  209.  
  210. void precom(int c=MOD){
  211. fact[0] = 1;
  212. FORE(i, 1, FACSZ) fact[i] = mul(fact[i-1], i, c);
  213. ifact[FACSZ-1] = mod_inverse(fact[FACSZ-1], c);
  214. REPD(i, FACSZ-1){
  215. ifact[i] = mul(i+1, ifact[i+1], c);
  216. }
  217. }
  218.  
  219. int ncr(int n, int r, int c = MOD) {
  220. return mul(mul(ifact[r], ifact[n-r], c), fact[n], c);
  221. }
  222.  
  223. template<class A> void read(vt<A>& v);
  224. template<class A, size_t S> void read(ar<A, S>& a);
  225. template<class T> void read(T& x) {
  226. cin >> x;
  227. }
  228. void read(double& d) {
  229. string t;
  230. read(t);
  231. d=stod(t);
  232. }
  233. void read(long double& d) {
  234. string t;
  235. read(t);
  236. d=stold(t);
  237. }
  238. template<class H, class... T> void read(H& h, T&... t) {
  239. read(h);
  240. read(t...);
  241. }
  242. template<class A> void read(vt<A>& x) {
  243. EACH(a, x)
  244. read(a);
  245. }
  246. template<class A, size_t S> void read(array<A, S>& x) {
  247. EACH(a, x)
  248. read(a);
  249. }
  250.  
  251. string to_string(char c) {
  252. return string(1, c);
  253. }
  254. string to_string(bool b) {
  255. return b?"true":"false";
  256. }
  257. string to_string(const char* s) {
  258. return string(s);
  259. }
  260. string to_string(string s) {
  261. return s;
  262. }
  263. string to_string(vt<bool> v) {
  264. string res;
  265. FOR(sz(v))
  266. res+=char('0'+v[i]);
  267. return res;
  268. }
  269.  
  270. template<size_t S> string to_string(bitset<S> b) {
  271. string res;
  272. FOR(S)
  273. res+=char('0'+b[i]);
  274. return res;
  275. }
  276. template<class T> string to_string(T v) {
  277. bool f=1;
  278. string res;
  279. EACH(x, v) {
  280. if(!f)
  281. res+=' ';
  282. f=0;
  283. res+=to_string(x);
  284. }
  285. return res;
  286. }
  287.  
  288. template<class A> void write(A x) {
  289. cout << to_string(x);
  290. }
  291. template<class H, class... T> void write(const H& h, const T&... t) {
  292. write(h);
  293. write(t...);
  294. }
  295. void print() {
  296. write("\n");
  297. }
  298. template<class H, class... T> void print(const H& h, const T&... t) {
  299. write(h);
  300. if(sizeof...(t))
  301. write(' ');
  302. print(t...);
  303. }
  304.  
  305. template<class T> void offset(ll o, T& x) {
  306. x+=o;
  307. }
  308. template<class T> void offset(ll o, vt<T>& x) {
  309. EACH(a, x)
  310. offset(o, a);
  311. }
  312. template<class T, size_t S> void offset(ll o, ar<T, S>& x) {
  313. EACH(a, x)
  314. offset(o, a);
  315. }
  316.  
  317. mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
  318. ll randint(ll a, ll b) {
  319. return uniform_int_distribution<ll>(a, b)(mt_rng);
  320. }
  321.  
  322. template<class T, class U> void vti(vt<T> &v, U x, size_t n) {
  323. v=vt<T>(n, x);
  324. }
  325. template<class T, class U> void vti(vt<T> &v, U x, size_t n, size_t m...) {
  326. v=vt<T>(n);
  327. EACH(a, v)
  328. vti(a, x, m);
  329. }
  330.  
  331. /****************** Geometry *****************/
  332. template <typename T> inline T PointDistanceHorVer(T x1,T y1,T x2, T y2)
  333. {return abs(x1-x2)+abs(y1-y2);}
  334. template <typename T> inline T PointDistanceDiagonally(T x1,T y1,T x2, T y2)
  335. {return sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));}
  336. template <typename T> inline T PointDistanceMinimum(T x1,T y1,T x2, T y2)
  337. { T tmp1=abs(x1-x2); T tmp2=abs(y1-y2); T tmp3=abs(tmp1-tmp2);
  338. T tmp4=min(tmp1, tmp2); return tmp3+tmp4; }
  339. template <typename T> inline T PointDistance3D(T x1,T y1,T z1,T x2,T y2,T z2)
  340. {return sqrt(square(x2-x1)+square(y2-y1)+square(z2-z1));}
  341.  
  342. template <typename T> inline T Cube(T a){return a*a*a;}
  343. template <typename T> inline T RectengularPrism(T a,T b,T c)
  344. {return a*b*c;}
  345. template <typename T> inline T Pyramid(T base, T height)
  346. {return (1/3)*base*height;}
  347. template <typename T> inline T Ellipsoid(T r1,T r2,T r3)
  348. {return (4/3)*PI*r1*r2*r3;}
  349. template <typename T> inline T IrregualarPrism(T base, T height)
  350. {return base*height;}
  351. template <typename T> inline T Sphere(T radius)
  352. { return (4/3)*PI*radius*radius*radius;}
  353. template <typename T> inline T CylinderB(T base, T height)
  354. {return base*height;} // base and height
  355. template <typename T> inline T CylinderR(T radius, T height)
  356. {return PI*radius*radius*height;} // radius and height
  357. template <typename T> inline T Cone (T radius,T base, T height)
  358. {return (1/3)*PI*radius*radius*height;}
  359. /****************** Geometry end *****************/
  360.  
  361. const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
  362. const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
  363.  
  364. void solve() {
  365. }
  366.  
  367. int main() {
  368. ios_base::sync_with_stdio(0);
  369. cin.tie(0);
  370. cout.tie(0);
  371.  
  372. int t=1;
  373. read(t);
  374. FOR(t) {
  375. write("Case #", i+1, ": ");
  376. solve();
  377. }
  378. }
  379.  
  380.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement