API tools faq
paste
Sayach8

Untitled

Sayach8
Oct 9th, 2021
15
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.69 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #define gp __gnu_pbds
  4. #define iset(T) gp::tree<T,gp::null_type,less<T>,gp::rb_tree_tag,gp::tree_order_statistics_node_update>
  5. using namespace std;
  6.  
  7. #define SQ(x) ((x)*(x))
  8. #define u unsigned
  9. #define ull unsigned long long
  10. #define ll long long
  11. #define ld long double
  12. #define test(x) cerr<<"here "<<#x<<endl;
  13. #define putpls(x) #x
  14. #define casing(x,y) cout<<"Case #"<<x<<": "<<y<<'\n';
  15. #define inputstl(v) for(auto& x:v) cin>>x;
  16. #define input(arr,n) for(ull i=0;i<n;++i){cin>>(arr)[i];}
  17. #define print(arr,n) for(ull i=0;i<n;++i){cout<<(arr)[i]<<" ";}cout<<'\n';
  18. #define printall(x) {for(auto y:x){cout<<y<<' ';}cout<<'\n';}
  19. #define printallpii(x) for(auto y:x){cout<<y.fi<<','<<y.se<<' ';}cout<<'\n';
  20. #define print_err(arr,n) for(ull i=0;i<n;++i){cerr<<(arr)[i]<<" ";}cerr<<'\n';
  21. #define printall_err(x) for(auto y:x){cerr<<y<<' ';}cerr<<'\n';
  22. #define printallpii_err(x) for(auto y:x){cerr<<y.fi<<','<<y.se<<' ';}cerr<<'\n';
  23. #define fi first
  24. #define se second
  25. #define pb push_back
  26. #define eb emplace_back
  27. #define mp make_pair
  28. #define mt make_tuple
  29. #define pii pair<int,int>
  30. #define pll pair<long long,long long>
  31. #define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  32. #define SENSITIVITY 1e-9
  33. #define EQUAL(xx1,xx2) [](auto x1,auto x2){double ep=0.0001;double pos=x1-x2;if(pos<0){pos=-pos;}double maxi=(x1>x2)?(x1):(x2);if(pos/(maxi*ep)<SENSITIVITY)return true;else return false;}(xx1,xx2)
  34. #define pack(x) x.begin(),x.end()
  35.  
  36. constexpr int64_t mod=1e9+7;
  37.  
  38. struct timer
  39. {
  40. private:
  41. static int __timer_number;
  42. public:
  43. int timer_number;
  44. chrono::high_resolution_clock::time_point t1;
  45. timer(): t1(chrono::high_resolution_clock::now()),timer_number(__timer_number++)
  46. {
  47. cout<<"timer number "<<timer_number<<" init\n";
  48. }
  49. timer(const timer& t):t1(t.t1),timer_number(__timer_number++)
  50. {
  51. cout<<"timer number "<<timer_number<<" init\n";
  52. }
  53. template<class T=chrono::milliseconds>
  54. auto give_time()
  55. {
  56. chrono::high_resolution_clock::time_point t2;
  57. t2=chrono::high_resolution_clock::now();
  58. return chrono::duration_cast<T>(t2-t1);
  59. }
  60. template<class T=chrono::milliseconds>
  61. void print_time()
  62. {
  63. chrono::high_resolution_clock::time_point t2;
  64. t2=chrono::high_resolution_clock::now();
  65. auto d=chrono::duration_cast<T>(t2-t1);
  66. cout<<"time (default:milli) until now by timer "<<timer_number<<" : "<<d.count()<<'\n';
  67. }
  68. ~timer()
  69. {
  70. __timer_number--;
  71. }
  72. };
  73. int timer::__timer_number=0;
  74.  
  75. //this does not support . character matching (globbing)
  76. //to do that add the code from your solution of leetcode 211
  77. //add a new static element to the node, named defaulter and use that for globbing
  78.  
  79. template<class T>
  80. class trie{
  81. private:
  82. vector<T> hold;
  83. int hold_size;
  84. int found;
  85. int _size;
  86. struct node{
  87. map<T,node*> link;
  88. int ending;
  89. node():link(map<T,node*>()),ending(0)
  90. {
  91.  
  92. }
  93. ~node()
  94. {
  95.  
  96. }
  97. };
  98. node root;
  99. void __traverse(node* const p,int index)
  100. {
  101. if(index==hold_size)
  102. {
  103. // if(p->ending>0)
  104. // found=;
  105. found=p->ending;
  106. return ;
  107. }
  108. // if(hold[index]=='.')
  109. // {
  110. // for(auto& x:p->link)
  111. // {
  112. // traverse(x.second,index+1);
  113. // if(found)
  114. // return ;
  115. // }
  116. // }
  117. // else
  118. // {
  119. auto it=p->link.find(hold[index]);
  120. if(it!=p->link.end())
  121. {
  122. __traverse(it->second,index+1);
  123. }
  124. // }
  125. }
  126. bool __del_traverse(node* const p,int index)
  127. {
  128. if(index==hold_size)
  129. {
  130. if(!p->ending)
  131. {
  132. --p->ending;
  133. return 1;
  134. }
  135. return 0;
  136. }
  137. auto it=p->link.find(hold[index]);
  138. if(it!=p->link.end())
  139. {
  140. return __del_traverse(it->second,index+1);
  141. }
  142. return 0;
  143. }
  144. void __dfs_clear(node* const p)
  145. {
  146. for(auto& x:p->link)
  147. {
  148. __dfs_clear(x.second);
  149. delete x.second;
  150. }
  151.  
  152. }
  153. public:
  154. trie():_size(0)
  155. {
  156.  
  157. }
  158. void add_stuff(const vector<T>& v)
  159. {
  160. hold.assign(v.begin(),v.end());
  161. hold_size=v.size();
  162. int index=0;
  163. node* cur=&root;
  164. while(index!=hold_size)
  165. {
  166. auto it=cur->link.find(hold[index]);
  167. if(it==cur->link.end())
  168. {
  169. // test(1);
  170. cur->link[hold[index]]=new node();
  171. // cur=cur->link[hold[index]];
  172. }
  173. cur=cur->link[hold[index]];
  174. ++index;
  175. }
  176. ++(cur->ending);
  177. ++_size;
  178. }
  179. int find_stuff(const vector<T>& v)
  180. {
  181. found=0;
  182. hold.assign(v.begin(),v.end());
  183. hold_size=v.size();
  184. __traverse(&root,0);
  185. return found;
  186. }
  187. bool delete_stuff(const vector<T>& v)
  188. {
  189. hold.assign(v.begin(),v.end());
  190. hold_size=v.size();
  191. auto val=__del_traverse(&root,0);
  192. if(val)
  193. --_size;
  194. return val;
  195. }
  196. void clear()
  197. {
  198. __dfs_clear(&root);
  199. root.link.clear();
  200. _size=0;
  201. }
  202. int size()
  203. {
  204. return _size;
  205. }
  206. ~trie()
  207. {
  208. clear();
  209. }
  210. };
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217. template<class A>
  218. void ____internal__print(string s,A a)
  219. {
  220. auto index=s.find(',');
  221. cerr<<s.substr(0,index)<<": "<<a<<'\n';
  222. }
  223. template<class A,class ... B>
  224. void ____internal__print(string s,A a,B... b)
  225. {
  226. auto index=s.find(',');
  227. cerr<<s.substr(0,index)<<": "<<a<<", ";
  228. ____internal__print(s.substr(index+1,(int)s.length()-index-1),b...);
  229. }
  230.  
  231. #define debug(...) \
  232. {string __debug__s__=string(#__VA_ARGS__)+",";____internal__print(__debug__s__,__VA_ARGS__);}
  233.  
  234. bool isPrime(ll a)
  235. {
  236. if(a==1)
  237. return false;
  238. for(ll i=2; i*i<=a; ++i)
  239. {
  240. if(a%i==0)
  241. {
  242. return false;
  243. }
  244. }
  245. return true;
  246. }
  247. bool isPali(string s)
  248. {
  249. int _size=(s.length())/2;
  250. for(int i=0; i<_size; ++i)
  251. {
  252. if(s.at(i)!=s.at(s.length()-1-i))
  253. {
  254. return false;
  255. }
  256. }
  257. return true;
  258. }
  259. int gcd(int a,int b)
  260. {
  261. if(a==0)
  262. {
  263. return b;
  264. }
  265. else if(b==0)
  266. {
  267. return a;
  268. }
  269. else
  270. {
  271. int shift=__builtin_ctz(a|b);
  272. a>>=__builtin_ctz(a);
  273. do
  274. {
  275. b>>=__builtin_ctz(b);
  276. if(a>b)
  277. {
  278. a=a^b;
  279. b=a^b;
  280. a=a^b;
  281. }
  282. b-=a;
  283. }
  284. while(b);
  285. return a<<shift;
  286. }
  287. }
  288. ll gcdll(ll a,ll b)
  289. {
  290. if(a==0)
  291. {
  292. return b;
  293. }
  294. else if(b==0)
  295. {
  296. return a;
  297. }
  298. else
  299. {
  300. ll shift=__builtin_ctzll(a|b);
  301. a>>=__builtin_ctzll(a);
  302. do
  303. {
  304. b>>=__builtin_ctzll(b);
  305. if(a>b)
  306. {
  307. a=a^b;
  308. b=a^b;
  309. a=a^b;
  310. }
  311. b-=a;
  312. }
  313. while(b);
  314. return a<<shift;
  315. }
  316. }
  317. ll power(ll a,ll b,ll _mod)
  318. {
  319. a%=_mod;
  320. ll temp=a;
  321. ll ans=1;
  322. if(!b)
  323. return 1;
  324. int limit=63-__builtin_clzll(b);
  325. int index=0;
  326. while(index<=limit)
  327. {
  328. if(b&(1ll<<index))
  329. {
  330. ans=(ans*temp)%_mod;
  331. }
  332. ++index;
  333. temp=(temp*temp)%_mod;
  334. }
  335. return ans;
  336. }
  337. template<class T>
  338. inline void swapper(const T& d1,const T& d2)
  339. {
  340. for(int i=0;i<sizeof(T);++i)
  341. {
  342. *((char*)(&d1)+i)=(*((char*)(&d1)+i))^(*((char*)(&d2)+i));
  343. }
  344. for(int i=0;i<sizeof(T);++i)
  345. {
  346. *((char*)(&d2)+i)=(*((char*)(&d1)+i))^(*((char*)(&d2)+i));
  347. }
  348. for(int i=0;i<sizeof(T);++i)
  349. {
  350. *((char*)(&d1)+i)=(*((char*)(&d1)+i))^(*((char*)(&d2)+i));
  351. }
  352. }
  353.  
  354. int kmp(const string& s,const string& t)
  355. {
  356. int s_size=s.size(),t_size=t.size();
  357. if(s_size<t_size)
  358. return 0;
  359. vector<int> arr(t_size);
  360. int len=0;
  361. for(int i=0;i<t_size;++i)
  362. {
  363. if(!i)
  364. {
  365. arr[i]=0;
  366. continue;
  367. }
  368. while(1)
  369. {
  370. if(t[len]==t[i])
  371. {
  372. arr[i]=++len;
  373. break;
  374. }
  375. if(!len)
  376. {
  377. arr[i]=0;
  378. break;
  379. }
  380. len=arr[len-1];
  381. }
  382. }
  383. //printall(arr);
  384. int ans=0;
  385. for(int j=0,i=0;i<s_size;++i,++j)
  386. {
  387. // debug(i,j);
  388. if(s[i]==t[j])
  389. {
  390. if(j==t.length()-1)
  391. {
  392. //debug(i,j)
  393. j=arr[j]-1;
  394. //debug(j);
  395. ++ans;
  396. }
  397. continue;
  398. }
  399. if(!j)
  400. {
  401. --j;
  402. continue;
  403. }
  404. --i;
  405. j=arr[j-1]-1;
  406. }
  407. return ans;
  408. }
  409. template<class T>
  410. vector<T> LIS(vector<T> a)
  411. {
  412. int n=a.size();
  413. vector<pair<T,int>> v;
  414. vector<T*> add(n);
  415. add[0]=nullptr;
  416. v.push_back(make_pair(a[0],0));
  417. auto f=[](pair<T,int> a,pair<T,int> b){return a.first<b.first;};
  418. for(int i=1;i<n;++i)
  419. {
  420. auto it=lower_bound(v.begin(),v.end(),make_pair(a[i],-1),f);
  421. if(it==v.end())
  422. {
  423. add[i]=&a[0]+v.back().second;
  424. v.push_back(make_pair(a[i],i));
  425. }
  426. else
  427. {
  428. it->first=a[i];
  429. it->second=i;
  430. if(it==v.begin())
  431. {
  432. add[i]=nullptr;
  433. }
  434. else
  435. {
  436. add[i]=&a[0]+(it-1)->second;
  437. }
  438. }
  439. }
  440. vector<T> ans;
  441. ans.reserve(v.size());
  442. T* p=&a[0]+v.back().second;
  443. while(p!=nullptr)
  444. {
  445. ans.push_back(*p);
  446. p=(add[p-&a[0]]);
  447. }
  448. reverse(ans.begin(),ans.end());
  449. return ans;
  450. }
  451.  
  452. ///O(N*N) NOT MANCHAR . BULLSHIT DP
  453. string longest_palindromic_substring(const string& s)
  454. {
  455. if(s.size()<=1)
  456. return s;
  457. int len=s.size();
  458. vector<bool> odd(s.size(),1);
  459. vector<bool> even(s.size(),0);
  460. string ans=string(1,s[0]);
  461. for(int i=0;i<len-1;++i)
  462. {
  463. if(s[i]==s[i+1])
  464. {
  465. even[i]=1;
  466. if(ans.size()<2)
  467. ans=s.substr(i,2);
  468. }
  469. }
  470. for(int i=3;i<=len;++i)
  471. {
  472. if(i&1)
  473. {
  474. for(int j=0;j<=len-i;++j)
  475. {
  476. odd[j]=(s[j]==s[j+i-1])&&(odd[j+1]);
  477. if(odd[j]&&ans.size()<i)
  478. ans=s.substr(j,i);
  479. }
  480. }
  481. else
  482. {
  483. for(int j=0;j<=len-i;++j)
  484. {
  485. even[j]=(s[j]==s[j+i-1])&&(even[j+1]);
  486. if(even[j]&&ans.size()<i)
  487. ans=s.substr(j,i);
  488. }
  489. }
  490. }
  491. return ans;
  492. }
  493.  
  494.  
  495. template<class S>
  496. S longestSubarraySum(auto start,auto end)
  497. {
  498. S val=0;
  499. S maxi=*start;
  500. for(auto s=start;s!=end;++s)
  501. {
  502. if(val+*s>=*s)
  503. {
  504. val+=*s;
  505. }
  506. else
  507. {
  508. val=*s;
  509. }
  510. if(maxi<val)
  511. {
  512. maxi=val;
  513. }
  514. }
  515. return maxi;
  516. }
  517.  
  518. template<class T>
  519. T fibo(T x,T _mod)
  520. {
  521. if(x==1)
  522. {
  523. return (T)0;
  524. }
  525. else if(x==2)
  526. {
  527. return (T)1;
  528. }
  529. // x*=2;// made it twice to get the actual value
  530. stack<pair<T,T>> st;
  531. while(x>1)
  532. {
  533. st.push(make_pair(x,x+1));
  534. x/=2;
  535. }
  536. //start with an even means the same components
  537. //otherwise component change
  538. T a=0;
  539. T b=1;
  540. T c;
  541. while(st.size())
  542. {
  543. auto p=st.top();
  544. st.pop();
  545. T cur_a;
  546. T cur_b;
  547. if(p.first&1)
  548. {
  549. cur_a=(b*b+2*a*b)%_mod;
  550. b=(a+b)%_mod;
  551. a=(b-a+_mod)%_mod;
  552. cur_b=(a*a+b*b)%_mod;
  553. }
  554. else
  555. {
  556. cur_a=(a*a+b*b)%_mod;
  557. cur_b=(b*b+2*a*b)%_mod;
  558. }
  559. a=cur_a;
  560. b=cur_b;
  561. }
  562. return a;
  563. }
  564.  
  565. // #pragma GCC optimize("Ofast")
  566. // #pragma GCC optimize("unroll-loops")
  567.  
  568.  
  569. int main()
  570. {
  571. // #ifdef ONLINE_JUDGE
  572. // #include <sys/resource.h>
  573. // rlimit R;
  574. // getrlimit(RLIMIT_STACK, &R);
  575. // R.rlim_cur = R.rlim_max;
  576. // setrlimit(RLIMIT_STACK, &R);
  577. // #endif
  578. //define cin fin
  579. //ifstream fin;
  580. //fin.open("input.txt",ios_base::in);
  581.  
  582. // fastio;
  583. // freopen("input.txt","r",stdin);
  584. //freopen("output.txt","w",stdout);
  585. int tt=1;
  586. cin>>tt;
  587. // scanf("%d",&tt);
  588. // timer t;
  589. int ittt=1;
  590. //////CHECK FOR EDGE CASES DUMMY!!!!!!!!!!!/////
  591. while(tt--)
  592. {
  593. int64_t n,k;
  594. cin>>n>>k;
  595. vector<int64_t> v(n);
  596. inputstl(v);
  597. sort(pack(v));
  598. vector<int64_t>presum(n+1);
  599. for(int i=0;i<n;++i)
  600. {
  601. presum[i+1]=v[i]+presum[i];
  602. }
  603. int equal_val=v[0];
  604. int quantity=1;
  605. // printall(v);
  606. for(int i=1;i<n;++i)//vector
  607. {
  608. auto validate=[&](int x){//x is the index
  609. int64_t summing=presum[i]-presum[x];
  610. // debug(i,x,k,(i-x)*v[i]-summing);
  611. if((i-x)*v[i]-summing<=k)
  612. return 1;
  613. else
  614. return 0;
  615. };
  616. int start=0;
  617. int end=i-1;
  618. while(start!=end)
  619. {
  620. auto mid=(start+end)/2;
  621. if(validate(mid))
  622. {
  623. end=mid;
  624. }
  625. else
  626. {
  627. start=mid+1;
  628. }
  629. }
  630. // debug(i,start);
  631. if(quantity<i-start+1)
  632. {
  633. quantity=i-start+1;
  634. equal_val=v[i];
  635. }
  636. }
  637. cout<<quantity<<" "<<equal_val<<"\n";
  638. }
  639. // t.print_time();
  640. return 0;
  641. }
  642.  
Add Comment
Please, Sign In to add comment
Public Pastes
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!