API tools faq
paste
Advertisement
clown1337

Untitled

clown1337
Feb 25th, 2023
78
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 16.77 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <set>
  5. #include <map>
  6. #include <unordered_map>
  7. #include <unordered_set>
  8. #include <queue>
  9. #include <deque>
  10. #include <stack>
  11. #include <cmath>
  12. #include <numeric>
  13. #include <algorithm>
  14. #include <random>
  15. #include <fstream>
  16. #include <iomanip>
  17. #include <limits>
  18. #include <bitset>
  19. #include <ostream>
  20. #include <sstream>
  21. #include <cstring>
  22. #include <cassert>
  23.  
  24. using namespace std;
  25. /// Pragmas ///
  26. //#pragma GCC optimize("Ofast")
  27. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
  28. //#pragma GCC optimize("unroll-loops")
  29. /// define ///
  30. #define pii pair<int,int>
  31. #define V vector
  32. #define MP make_pair
  33. #define vi vector<int>
  34. #define ff first
  35. #define ss second
  36. #define vl vector<long long>
  37. /// typedef ///
  38. typedef long long ll;
  39. typedef long double ld;
  40.  
  41. /// solve ///
  42. #define int long long
  43. // consts
  44. const double PI = acos(-1);
  45. const ll MOD = 1000000007;
  46. const ll MOD2 = 1000000009;
  47. //const int p = 239;
  48. const long long inf = 1000000000 + 9;
  49. const int N = 150000+5000;
  50. const double eps = 1e-18;
  51. int dx[8] = {1,0,-1,0,1,-1,-1,1};
  52. int dy[8] = {0,1,0,-1,1,1,-1,-1};
  53.  
  54.  
  55.  
  56. //vector <int> cl(N);
  57. //vector <vector <int>> g(N);
  58. //vector <bool> used(N);
  59. //vector <int> dist(N);
  60. //vector <bool> blocked(N);
  61. //vector <bool> stop(N);
  62. //// ----------------------- DFS ------------------------------
  63. //void dfs(int v) {
  64. // used[v] = true;
  65. // if (g[v].size() == 1) {
  66. // int i = q[v].first;
  67. // int j = q[v].second;
  68. // ans.push_back({i, j});
  69. // return;
  70. // }
  71. // for (int i = 0; i < g[v].size(); ++i) {
  72. // int u = g[v][i];
  73. // if (!used[u])
  74. // dfs(u);
  75. // }
  76. //}
  77. // ----------------------- END DFS ------------------------------
  78.  
  79. // ----------------------- BFS ------------------------------
  80. ////vector <vector <ll>> g(N);
  81. //bool used[N];
  82. //bool used2[1000][1000];
  83. //ll dist[100][1e5];
  84. //map <pair<int,int>,int> m1;
  85. //void bfs(ll x, ll y, vector<vector<char>> &edge, int n, int x2, int y2) {
  86. // m1[{x,y}]++;
  87. // queue <pair<int,int>> q;
  88. // q.push({x,y});
  89. // while (!q.empty()) {
  90. // pair<int,int> v = q.front();
  91. // q.pop();
  92. // if (v.first == x2 && v.second == y2) {
  93. // return;
  94. // }
  95. // int sz1 = edge[v.first].size();
  96. // for (int i = 0; i < 4; ++i) {
  97. // if (v.second + dy[i] < 0 || v.first +dx[i] >= n || v.first + dx[i] < 0 || m1[{v.first + dx[i], v.second + dy[i]}] != 0) continue;
  98. // if (edge[v.first].size() <= v.second) continue;
  99. // int sz2 = edge[v.first + dx[i]].size();
  100. // if (sz1 == sz2) {
  101. // m1[{v.first+dx[i],v.second+dy[i]}]++;
  102. // dist[v.first+dx[i]][v.second+dy[i]] = dist[v.first][v.second] + 1;
  103. // q.push({v.first+dx[i], v.second+dy[i]});
  104. // } else if (sz1 > sz2 && dx[i] == -1) { // up
  105. // if (v.second + dy[i] >= sz2 && !used2[v.first+dx[i]][sz2-1]) {
  106. // used2[v.first+dx[i]][sz2-1] = true;
  107. // dist[v.first+dx[i]][sz2-1] = dist[v.first][v.second] + 1;
  108. // q.push({v.first+dx[i], sz2-1});
  109. // } else {
  110. // if (used2[v.first+dx[i]][v.second+dy[i]]) continue;
  111. // m1[{v.first+dx[i],v.second+dy[i]}]++;
  112. // dist[v.first+dx[i]][v.second+dy[i]] = dist[v.first][v.second] + 1;
  113. // q.push({v.first+dx[i], v.second + dy[i]});
  114. // }
  115. // } else if (sz1 > sz2 && dx[i] == 1) { // down
  116. // if (v.second + dy[i] >= sz2 && !used2[v.first+dx[i]][sz2-1]) {
  117. // used2[v.first+dx[i]][sz2-1] = true;
  118. // dist[v.first+dx[i]][sz2-1] = dist[v.first][v.second] + 1;
  119. // q.push({v.first+dx[i], sz2-1});
  120. // } else {
  121. // if (used2[v.first+dx[i]][v.second+dy[i]]) continue;
  122. // m1[{v.first+dx[i],v.second+dy[i]}]++;
  123. // dist[v.first+dx[i]][v.second+dy[i]] = dist[v.first][v.second] + 1;
  124. // q.push({v.first+dx[i], v.second + dy[i]});
  125. // }
  126. // } else {
  127. // m1[{v.first+dx[i],v.second+dy[i]}]++;
  128. // dist[v.first+dx[i]][v.second+dy[i]] = dist[v.first][v.second] + 1;
  129. // q.push({v.first+dx[i], v.second+dy[i]});
  130. // }
  131. //// if (dist[18][5] != 0) {
  132. //// cout << 1;
  133. //// }
  134. // }
  135. // }
  136. //}
  137. // ----------------------- END BFS ------------------------------
  138.  
  139. // ----------------------- GEN PERMUNTATION ------------------------------
  140. //vector <int> cur;
  141. //void gen(int n, int pos) {
  142. // if (pos == n) {
  143. // for (int i = 0; i < n; ++i) {
  144. // cout << cur[i] << ' ';
  145. // }
  146. // cout << '\n';
  147. // return;
  148. // } else {
  149. // for (int i = 1; i <= n; ++i) {
  150. // if (!used[i]) {
  151. // used[i] = true;
  152. // cur.push_back(i);
  153. // gen(n, pos + 1);
  154. // cur.pop_back();
  155. // used[i] = false;
  156. // }
  157. // }
  158. // }
  159. //}
  160. //
  161. //
  162. // ----------------------- END GEN PERMUNTATION ------------------------------
  163.  
  164.  
  165. // ----------------------- GCD & LCM ------------------------------
  166.  
  167. ll gcd(ll a, ll b) {
  168. return (b ? gcd(b, a%b) : a);
  169. }
  170.  
  171. ll lcm(ll a, ll b) {
  172. return a / gcd(a, b) * b;
  173. }
  174. //// ----------------------- END GCD & LCM ------------------------------
  175. //
  176. //
  177. //double euclid(int x1, int y1, int x2, int y2) {
  178. // return sqrt(abs((x2-x1) * (x2-x1)) + abs((y2-y1) * (y2-y1)));
  179. //}
  180. //
  181. //
  182. //// ----------------------- SIEVE ------------------------------
  183. //vector<bool> isPrime(1e6 + 7, true);
  184. //void sieve(){
  185. // isPrime[0] = isPrime[1] = false;
  186. // for(int i = 2; i * i <= 1e6 + 7; ++i){
  187. // if(isPrime[i]){
  188. // for(int j = i * i; j <= 1e5 + 7; j += i)
  189. // isPrime[j] = false;
  190. // }
  191. // }
  192. //}
  193. //// ----------------------- END SIEVE ------------------------------
  194. //
  195. //
  196. //// ----------------------- CountDivisors ------------------------------
  197. //int countDivisors(int n){
  198. // int ans = 2;
  199. // for(int i = 2; i * i <= n; i++){
  200. // if(n % i == 0) ans += 2;
  201. // if(i*i == n) ans--;
  202. // }
  203. // return ans;
  204. //}
  205. //// ----------------------- END CountDivisors ------------------------------
  206. //
  207. //// ----------------------- RETURN PRIME FACTORS VECTOR ------------------------------
  208. //vector <ll> fact(ll n) {
  209. // vector <ll> f;
  210. // for (int i = 2; i * i <= n; ++i)
  211. // while (n % i == 0) f.push_back(i), n /= i;
  212. // if (n > 1) f.push_back(n);
  213. // return f;
  214. //}
  215. //
  216. //vector<ll> priFactors(ll a){
  217. // vector<ll> answer;
  218. // while(a%2==0){
  219. // answer.push_back(2);
  220. // a/=2;
  221. // }
  222. // for(int i=3; i*i<=a; i+=2){
  223. // while(a%i == 0){
  224. // answer.push_back(i);
  225. // a /= i;
  226. // }
  227. // }
  228. // if(a>2) answer.push_back(a);
  229. // return answer;
  230. //}
  231. //// ----------------------- END RETURN PRIME FACTORS VECTOR ------------------------------
  232. //
  233. //
  234. //// ----------------------- VECTORS FOR GEOMETRY ------------------------------
  235. //typedef double T;
  236. //struct Vector {
  237. // T x, y;
  238. // Vector(T x=0, T y=0) : x(x), y(y) {}
  239. // Vector(Vector a, Vector b) : x(b.x - a.x), y(b.y - a.y) {}
  240. //
  241. // Vector operator-(const Vector& a) const {
  242. // return {x - a.x, y - a.y};
  243. // }
  244. // T len2() {
  245. // return x*x + y*y;
  246. // }
  247. // T len() {
  248. // return sqrt(len2());
  249. // }
  250. // //|A| * |B| * cos
  251. // //|A| * |B| * sin
  252. // T Dpr(const Vector& b) const {
  253. // return x * b.x + y * b.y;
  254. // }
  255. // T Cpr(const Vector& b) const {
  256. // return x*b.y - b.x*y;
  257. // }
  258. //};
  259. // ----------------------- END VECTORS FOR GEOMETRY ------------------------------
  260.  
  261.  
  262. // ----------------------- DIJKSTRA ------------------------------
  263. //
  264. ////vector <vector <pair<ll,ll>>> g(500); // w, from, to;
  265. ////vector <ll> dist(100100, inf);
  266. ////vector <ll> p(100100, inf);
  267. ////vector <bool> used(100100);
  268. ////vector <ll> path;
  269. ////vector <ll> par(500);
  270. ////vector <ll> lh(500);
  271. //
  272. //
  273. ////void dijkstra(ll s) {
  274. //// dist[s] = 0;
  275. //// set <pair<ll,ll>> q;
  276. //// q.emplace(dist[s], s);
  277. //// while (!q.empty()) {
  278. //// ll v = q.begin()->second;
  279. //// q.erase(q.begin());
  280. //// for (int i = 0; i < g[v].size(); ++i) {
  281. //// ll u = g[v][i].second;
  282. //// ll len = g[v][i].first;
  283. //// if (dist[u] < dist[v] + len) {
  284. //// q.erase({dist[u], u});
  285. //// dist[u] = dist[v] + len;
  286. //// q.emplace(dist[u], u);
  287. //// }
  288. //// }
  289. //// }
  290. ////}
  291. // ----------------------- END DIJKSTRA ------------------------------
  292.  
  293.  
  294. // ----------------------- DSU ------------------------------
  295.  
  296. //vector <int> dsu_par(1e5+50000);
  297. //vector <int> dsu_sz(1e5+50000);
  298. //
  299. //ll dsu_setId(ll v) {
  300. // if (dsu_par[v] == v)
  301. // return v;
  302. // else
  303. // return dsu_par[v] = dsu_setId(dsu_par[v]);
  304. //}
  305. //
  306. //void dsu_union(ll a, ll b) {
  307. // ll x = dsu_setId(a);
  308. // ll y = dsu_setId(b);
  309. // if (dsu_sz[x] < dsu_sz[y])
  310. // swap(x,y);
  311. // dsu_par[x] = y;
  312. // dsu_sz[x] += dsu_sz[y];
  313. //}
  314. //
  315. //bool dsu_check(ll a, ll b) {
  316. // if (dsu_setId(a) == dsu_setId(b)) {
  317. // return true;
  318. // } else {
  319. // return false;
  320. // }
  321. //}
  322. // ----------------------- END DSU ------------------------------
  323.  
  324.  
  325. // ----------------------- Queue with min ------------------------------
  326. //struct Queue {
  327. // stack <int> st1, st2, st1_min, st2_min;
  328. // void push(int x) {
  329. // st1.push(x);
  330. // if (st1_min.empty())
  331. // st1_min.push(x);
  332. // else
  333. // st1_min.push(min(st1_min.top(), x));
  334. // }
  335. // void del_e() {
  336. // if (st1_min.empty() && st2_min.empty()) return;
  337. // if (!st2.empty()) {
  338. // st2.pop();
  339. // st2_min.pop();
  340. // return;
  341. // }
  342. // while (!st1.empty()) {
  343. // st2.push(st1.top());
  344. // if (st2_min.empty())
  345. // st2_min.push(st1.top());
  346. // else
  347. // st2_min.push(min(st2_min.top(), st1.top()));
  348. // st1.pop();
  349. // st1_min.pop();
  350. // }
  351. // st2.pop();
  352. // st2_min.pop();
  353. // }
  354. // int get_min() {
  355. // if (st1_min.empty() && st2_min.empty()) {
  356. // return -1;
  357. // } else if (st1_min.empty()) {
  358. // return st2_min.top();
  359. // } else if (st2_min.empty()) {
  360. // return st1_min.top();
  361. // } else {
  362. // return min(st1_min.top(), st2_min.top());
  363. // }
  364. // }
  365. //};
  366. // ----------------------- END Queue with min ------------------------------
  367. // ----------------------- BINPOW ------------------------------
  368. //int binPow(int x, int n) {
  369. // if (n == 0) {
  370. // return 1;
  371. // } else {
  372. // if (n % 2 == 0) {
  373. // int a = binPow(x, n/2);
  374. // return (a*a);
  375. // } else {
  376. // return ((binPow(x, n-1) * x));
  377. // }
  378. // }
  379. //}
  380. //// ----------------------- END BINPOW ------------------------------
  381. //bool Prime(int n)
  382. //{
  383. // if (n <= 1)
  384. // return false;
  385. // if (n <= 3)
  386. // return true;
  387. // if (n % 2 == 0 || n % 3 == 0)
  388. // return false;
  389. //
  390. // for (int i = 5; i * i <= n; i = i + 6)
  391. // if (n % i == 0 || n % (i + 2) == 0)
  392. // return false;
  393. //
  394. // return true;
  395. //}
  396.  
  397. //bool t[1000000+1000];
  398. //int f(int n, int x, vl &a) {
  399. // if (x >= 0 && t[x]) {
  400. // return dp[x];
  401. // } else if (x == 0) {
  402. // return 1;
  403. // } else if (x < 0) {
  404. // return 0;
  405. // } else {
  406. // ll sum = 0;
  407. // for (int i = 0; i < n; ++i) {
  408. // sum += f(n, x-a[i], a);
  409. // }
  410. // return sum;
  411. // }
  412. //}
  413.  
  414. //struct Tree {
  415. // vector <char> t;
  416. // ll size;
  417. // void init(ll n) {
  418. // size = 1;
  419. // while (size < n) size *= 2;
  420. // t.assign(2*size-1, 'z');
  421. // }
  422. //
  423. //
  424. //
  425. // void set(ll i, ll v, ll x, ll lx, ll rx) {
  426. // if (rx-lx == 1) {
  427. // t[x] = v;
  428. // return;
  429. // } else {
  430. // ll m = (lx + rx)/2;
  431. // if (i < m) {
  432. // set(i, v, 2*x+1, lx, m);
  433. // } else {
  434. // set(i, v, 2*x+2, m, rx);
  435. // }
  436. // t[x] = min(t[2*x+1], t[2*x+2]);
  437. // }
  438. // }
  439. //
  440. // void set(ll i, ll v) {
  441. // set(i, v, 0, 0, size);
  442. // }
  443. //
  444. // char mn(int l, int r, int x, int lx, int rx) {
  445. // if (l >= rx || lx >= r) {
  446. // return 'z';
  447. // }
  448. // if (lx >= l && rx <= r) {
  449. // return t[x];
  450. // }
  451. // ll m = (lx + rx) / 2;
  452. // ll s1 = mn(l, r, 2 * x + 1, lx, m);
  453. // ll s2 = mn(l, r, 2 * x + 2, m, rx);
  454. // return min(s1, s2);
  455. // }
  456. //
  457. // char mn(int l, int r) {
  458. // return mn(l, r, 0, 0, size);
  459. // }
  460. //
  461. //};
  462. //
  463. //struct segtree {
  464. //
  465. //// struct node {
  466. //// int seg;
  467. //// int pref;
  468. //// int suf;
  469. //// int sum;
  470. //// };
  471. //
  472. // vector <int> tree;
  473. // int size;
  474. //
  475. //// node combine(node a, node b) {
  476. //// return {
  477. //// max(a.seg, max(b.seg, a.suf + b.pref)),
  478. //// max(a.pref, a.sum + b.pref),
  479. //// max(b.suf, b.sum + a.suf),
  480. //// a.sum + b.sum
  481. //// };
  482. //// }
  483. //
  484. // //const node zero = {0, 0, 0, 0};
  485. //
  486. // void init(int n) {
  487. // size = 1;
  488. // while (size < n) size*=2;
  489. // tree.resize(size * 2 - 1, 0);
  490. // }
  491. //
  492. //// void build(vector <int>& a, int x, int lx, int rx) {
  493. //// if (rx - lx == 1) {
  494. //// if (lx < a.size()) {
  495. //// tree[x] = {
  496. //// (a[lx] > 0 ? a[lx] : 0),
  497. //// (a[lx] > 0 ? a[lx] : 0),
  498. //// (a[lx] > 0 ? a[lx] : 0),
  499. //// a[lx]
  500. //// };
  501. //// }
  502. //// return;
  503. //// }
  504. //// int m = (rx + lx)/2;
  505. //// build(a, 2*x+1, lx, m);
  506. //// build(a, 2*x+2, m, rx);
  507. //// tree[x] = combine(tree[2*x+1], tree[2*x+2]);
  508. //// }
  509. ////
  510. //// void build(vector <int>& a) {
  511. //// init(a.size());
  512. //// build(a, 0, 0, size);
  513. //// }
  514. //
  515. // void push(int x, int lx, int rx) {
  516. // if (rx - lx != 1) {
  517. // int m = (lx+rx)/2;
  518. // int len1 = m-lx+1;
  519. // int len2 = rx-m+1;
  520. // add[2*x+1] = add[2*x+2] = add[x];
  521. // if (add[x]) {
  522. // tree[2*x+1] = add[x];
  523. // tree[2*x+2] = add[x];
  524. // }
  525. // add[x] = 0;
  526. // }
  527. // }
  528. //
  529. // void set(int l, int r, int v, int x, int lx, int rx) {
  530. // push(x, lx, rx);
  531. // if (l >= rx || lx >= r) {
  532. // return;
  533. // }
  534. // if (lx >= l && rx <= r) {
  535. // tree[x] = v * (rx-lx);
  536. // add[x] = v;
  537. // return;
  538. // }
  539. // int m = (lx + rx)/2;
  540. // set(l, r, v, 2*x+1, lx, m);
  541. // set(l, r, v, 2*x+2, m, rx);
  542. // }
  543. //
  544. // void set(int l, int r, int v) {
  545. // set(l, r, v, 0, 0, size);
  546. // }
  547. //
  548. // int get_sum(int l, int r, int x, int lx, int rx) {
  549. // if (lx >= r || rx <= l) {
  550. // return 0;
  551. // }
  552. // if (lx >= l && rx <= r) {
  553. // return tree[x];
  554. // }
  555. // int m = (lx + rx)/2;
  556. // int sum1 = get_sum(l, r, 2*x+1, lx, m);
  557. // int sum2 = get_sum(l, r, 2*x+2, m, rx);
  558. // return sum1 + sum2;
  559. // }
  560. //
  561. // int get_sum(int l, int r) {
  562. // return get_sum(l, r, 0, 0, size);
  563. // }
  564. //
  565. //};
  566.  
  567. struct Vector {
  568. int x, y;
  569. Vector() {}
  570. Vector(int x1, int y1) {
  571. x = x1;
  572. y = y1;
  573. }
  574. Vector(Vector a, Vector b) {
  575. x = b.x - a.x;
  576. y = b.y - a.y;
  577. }
  578. Vector operator+(Vector other) const {
  579. return Vector(x + other.x, y + other.y);
  580. }
  581. Vector operator-(Vector other) const {
  582. return Vector(x - other.x, y - other.y);
  583. }
  584. Vector operator*(int d) {
  585. return Vector(x * d, y * d);
  586. }
  587. long long operator*(Vector other) const {
  588. return x * other.x + y * other.y;
  589. }
  590. long long operator^(Vector other) const {
  591. return x * other.y - y * other.x;
  592. }
  593. long long len2() {
  594. return x * x + y * y;
  595. }
  596. long long len() {
  597. return sqrt(len2());
  598. }
  599. };
  600. typedef Vector Point;
  601.  
  602. double Angle(Vector a, Vector b) {
  603. return atan2(a ^ b, a * b);
  604. }
  605.  
  606. double Dist(Vector a, Vector b) {
  607. return Vector(a, b).len();
  608. }
  609.  
  610. double Area(Point a, Point b, Point c) {
  611. Vector ab(a, b);
  612. Vector ac(a, c);
  613. return (double) abs(ab ^ ac) / 2;
  614. }
  615.  
  616. istream &operator>>(istream &in, Point &p) {
  617. in >> p.x >> p.y;
  618. return in;
  619. }
  620.  
  621. ostream &operator<<(ostream &out, Point p) {
  622. out << p.x << ' ' << p.y;
  623. return out;
  624. }
  625.  
  626. void solve() {
  627.  
  628. }
  629.  
  630.  
  631.  
  632. signed main() {
  633. ios_base::sync_with_stdio(false);
  634. cin.tie(NULL);
  635. // freopen("","r",stdin);
  636. // freopen("","w",stdout);
  637. int t = 1; // cin >> t;
  638. while (t--) solve();
  639. return 0;
  640. }
  641.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!