fork download
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC optimize("inline")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. template<class T> struct cLtraits_identity{
  7. using type = T;
  8. }
  9. ;
  10. template<class T> using cLtraits_try_make_unsigned =
  11. typename conditional<
  12. is_integral<T>::value,
  13. make_unsigned<T>,
  14. cLtraits_identity<T>
  15. >::type;
  16. void*wmem;
  17. char memarr[96000000];
  18. template<class S, class T> inline S chmin(S &a, T b){
  19. if(a>b){
  20. a=b;
  21. }
  22. return a;
  23. }
  24. template<class S, class T> inline S chmax(S &a, T b){
  25. if(a<b){
  26. a=b;
  27. }
  28. return a;
  29. }
  30. template<class S, class T> inline S divup_L(S a, T b){
  31. return (a+b-1)/b;
  32. }
  33. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  34. static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  35. (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  36. (*arr)=(T*)(*mem);
  37. (*mem)=((*arr)+x);
  38. }
  39. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  40. walloc1d(arr, x2-x1, mem);
  41. (*arr) -= x1;
  42. }
  43. inline int Ilog2_f_L(const int n){
  44. int res;
  45. if(n <= 0){
  46. return -1;
  47. }
  48. res = sizeof(int) * 8 - __builtin_clz(n) - 1;
  49. return res;
  50. }
  51. inline int Ilog2_f_L(const long long n){
  52. int res;
  53. if(n <= 0){
  54. return -1;
  55. }
  56. res = sizeof(long long) * 8 - __builtin_clzll(n) - 1;
  57. return res;
  58. }
  59. template<class T1> void sortI(int N, T1 a[], void *mem = wmem){
  60. sort(a, a+N);
  61. }
  62. template<class T1, class T2> void sortI(int N, T1 a[], T2 b[], void *mem = wmem){
  63. int i;
  64. pair<T1, T2>*arr;
  65. walloc1d(&arr, N, &mem);
  66. for(i=(0);i<(N);i++){
  67. arr[i].first = a[i];
  68. arr[i].second = b[i];
  69. }
  70. sort(arr, arr+N);
  71. for(i=(0);i<(N);i++){
  72. a[i] = arr[i].first;
  73. b[i] = arr[i].second;
  74. }
  75. }
  76. template<class T1, class T2, class T3> void sortI(int N, T1 a[], T2 b[], T3 c[], void *mem = wmem){
  77. int i;
  78. pair<T1, pair<T2, T3> >*arr;
  79. walloc1d(&arr, N, &mem);
  80. for(i=(0);i<(N);i++){
  81. arr[i].first = a[i];
  82. arr[i].second.first = b[i];
  83. arr[i].second.second = c[i];
  84. }
  85. sort(arr, arr+N);
  86. for(i=(0);i<(N);i++){
  87. a[i] = arr[i].first;
  88. b[i] = arr[i].second.first;
  89. c[i] = arr[i].second.second;
  90. }
  91. }
  92. template<class T1, class T2, class T3, class T4> void sortI(int N, T1 a[], T2 b[], T3 c[], T4 d[], void *mem = wmem){
  93. int i;
  94. pair<pair<T1, T2>, pair<T3, T4> >*arr;
  95. walloc1d(&arr, N, &mem);
  96. for(i=(0);i<(N);i++){
  97. arr[i].first.first = a[i];
  98. arr[i].first.second = b[i];
  99. arr[i].second.first = c[i];
  100. arr[i].second.second = d[i];
  101. }
  102. sort(arr, arr+N);
  103. for(i=(0);i<(N);i++){
  104. a[i] = arr[i].first.first;
  105. b[i] = arr[i].first.second;
  106. c[i] = arr[i].second.first;
  107. d[i] = arr[i].second.second;
  108. }
  109. }
  110. template<class T> inline int sort_helper_getbit(T A[]){
  111. return -1;
  112. }
  113. template<> inline int sort_helper_getbit(int A[]){
  114. return sizeof(int)*8;
  115. }
  116. template<> inline int sort_helper_getbit(unsigned A[]){
  117. return sizeof(unsigned)*8;
  118. }
  119. template<> inline int sort_helper_getbit(long long A[]){
  120. return sizeof(long long)*8;
  121. }
  122. template<> inline int sort_helper_getbit(unsigned long long A[]){
  123. return sizeof(unsigned long long)*8;
  124. }
  125. template<> inline int sort_helper_getbit(char A[]){
  126. return sizeof(char)*8;
  127. }
  128. template<class T> void sortA_1_int_L(int N, T A[], void *mem = wmem){
  129. int i;
  130. int j;
  131. int k;
  132. int b;
  133. int s;
  134. int ok;
  135. ok = 1;
  136. for(i=(1);i<(N);i++){
  137. if(A[i-1] > A[i]){
  138. ok = 0;
  139. break;
  140. }
  141. }
  142. if(ok){
  143. return;
  144. }
  145. if(N < 128){
  146. sort(A,A+N);
  147. return;
  148. }
  149. b = sort_helper_getbit(A);
  150. if(b==-1){
  151. sort(A,A+N);
  152. return;
  153. }
  154. T mn;
  155. T mx;
  156. mn = mx = A[0];
  157. for(i=(1);i<(N);i++){
  158. chmin(mn, A[i]);
  159. }
  160. for(i=(1);i<(N);i++){
  161. chmax(mx, A[i]);
  162. }
  163. ok = 1;
  164. if(mn < 0 && mx > 0 && (mn < -N || mx > N)){
  165. ok = 0;
  166. }
  167. if(ok && mx - mn > N){
  168. ok = 0;
  169. }
  170. if(ok){
  171. int*tmp;
  172. walloc1d(&tmp, mx-mn+1, &mem);
  173. for(i=(0);i<(mx-mn+1);i++){
  174. tmp[i] = 0;
  175. }
  176. for(i=(0);i<(N);i++){
  177. tmp[A[i]-mn]++;
  178. }
  179. k = 0;
  180. for(i=(0);i<(mx-mn+1);i++){
  181. while(tmp[i] > 0){
  182. tmp[i]--;
  183. A[k++] = i+mn;
  184. }
  185. }
  186. return;
  187. }
  188. {
  189. typename make_unsigned<T>::type *t[2];
  190. typename make_unsigned<T>::type mask;
  191. typename make_unsigned<T>::type cur;
  192. typename make_unsigned<T>::type one = 1;
  193. T tone = 1;
  194. int*pos;
  195. int nn = 0;
  196. int ss;
  197. s =Ilog2_f_L(N);
  198. if(s > 8){
  199. s = (8 + (s-7)/2);
  200. }
  201. ss = 1;
  202. for(;;){
  203. if(ss >= b){
  204. break;
  205. }
  206. if( mx >= 0 && (tone << (ss-1)) < mx ){
  207. ss++;
  208. continue;
  209. }
  210. if( mn < 0 && -(tone << (ss-1)) >= mn ){
  211. ss++;
  212. continue;
  213. }
  214. break;
  215. }
  216. k =(divup_L(ss,s));
  217. s =(divup_L(ss,k));
  218. mask = 0;
  219. for(i=(0);i<(b);i++){
  220. if(i < s*k){
  221. mask |= one << i;
  222. }
  223. }
  224. t[0] = (typename make_unsigned<T>::type *) A;
  225. walloc1d(&t[1], N, &mem);
  226. walloc1d(&pos, (1<<s)+1, &mem);
  227. for(j=(0);j<(k);j++){
  228. cur = 0;
  229. for(i=(0);i<(b);i++){
  230. if(s*j <= i && i < s*(j+1) && i < b){
  231. cur |= one << i;
  232. }
  233. }
  234. for(i=(0);i<((1<<s)+1);i++){
  235. pos[i] = 0;
  236. }
  237. for(i=(0);i<(N);i++){
  238. pos[((t[nn][i]&cur)>>(s*j))+1]++;
  239. }
  240. for(i=(0);i<((1<<s));i++){
  241. pos[i+1] += pos[i];
  242. }
  243. for(i=(0);i<(N);i++){
  244. t[nn^1][pos[(t[nn][i]&cur)>>(s*j)]++] = t[nn][i];
  245. }
  246. nn ^= 1;
  247. mask ^= cur;
  248. }
  249. if(mn < 0 && mx >= 0){
  250. k = 0;
  251. for(i=(0);i<(N);i++){
  252. if(A[i] < 0){
  253. k++;
  254. }
  255. }
  256. for(i=(0);i<(k);i++){
  257. t[nn^1][i] = t[nn][N-k+i];
  258. }
  259. for(i=(k);i<(N);i++){
  260. t[nn^1][i] = t[nn][i-k];
  261. }
  262. nn ^= 1;
  263. }
  264. if(nn==1){
  265. for(i=(0);i<(N);i++){
  266. t[0][i] = t[1][i];
  267. }
  268. }
  269. return;
  270. }
  271. sort(A, A+N);
  272. }
  273. template<class T> void sortA_1_nonint_L(int N, T A[], void *mem = wmem){
  274. sort(A,A+N);
  275. }
  276. template<class T> void sortA_1_call_L(int N, T A[], void *mem = wmem){
  277. sortA_1_nonint_L(N, A, mem);
  278. }
  279. template<> void sortA_1_call_L(int N, int A[], void *mem){
  280. sortA_1_int_L(N, A, mem);
  281. }
  282. template<> void sortA_1_call_L(int N, unsigned A[], void *mem){
  283. sortA_1_int_L(N, A, mem);
  284. }
  285. template<> void sortA_1_call_L(int N, long long A[], void *mem){
  286. sortA_1_int_L(N, A, mem);
  287. }
  288. template<> void sortA_1_call_L(int N, unsigned long long A[], void *mem){
  289. sortA_1_int_L(N, A, mem);
  290. }
  291. template<> void sortA_1_call_L(int N, char A[], void *mem){
  292. sortA_1_int_L(N, A, mem);
  293. }
  294. template<class T1> void sortA(int N, T1 a[], void *mem = wmem){
  295. sortA_1_call_L(N, a, mem);
  296. }
  297. template<class T1, class T2> void sortA_2_int_L(int N, T1 A[], T2 B[], void *mem = wmem){
  298. int i;
  299. int b_a;
  300. int b_b;
  301. int s1;
  302. int s2;
  303. int so2;
  304. T1 mn1;
  305. T1 mx1;
  306. T2 mn2;
  307. T2 mx2;
  308. typename cLtraits_try_make_unsigned<T1>::type r1;
  309. typename cLtraits_try_make_unsigned<T2>::type r2;
  310. so2 = 1;
  311. for(i=(1);i<(N);i++){
  312. if(A[i-1] > A[i] || (A[i-1]==A[i] && B[i-1] > B[i])){
  313. so2 = 0;
  314. break;
  315. }
  316. }
  317. if(so2){
  318. return;
  319. }
  320. so2 = 1;
  321. for(i=(1);i<(N);i++){
  322. if(A[i-1] > A[i]){
  323. so2 = 0;
  324. break;
  325. }
  326. }
  327. if(so2==1){
  328. int k = 0;
  329. for(i=(1);i<(N);i++){
  330. if(A[i] != A[i-1]){
  331. sortA_1_call_L(i-k, B+k, mem);
  332. k = i;
  333. }
  334. }
  335. sortA_1_call_L(N-k, B+k, mem);
  336. return;
  337. }
  338. if(N < 128){
  339. sortI(N,A,B,mem);
  340. return;
  341. }
  342. b_a = sort_helper_getbit(A);
  343. b_b = sort_helper_getbit(B);
  344. if(b_a == -1 || b_b == -1){
  345. sortI(N,A,B,mem);
  346. return;
  347. }
  348. mn1 = mx1 = A[0];
  349. for(i=(1);i<(N);i++){
  350. chmin(mn1, A[i]);
  351. }
  352. for(i=(1);i<(N);i++){
  353. chmax(mx1, A[i]);
  354. }
  355. mn2 = mx2 = B[0];
  356. for(i=(1);i<(N);i++){
  357. chmin(mn2, B[i]);
  358. }
  359. for(i=(1);i<(N);i++){
  360. chmax(mx2, B[i]);
  361. }
  362. if(mn1 < -4611686016279904256LL || mn2 < -4611686016279904256LL || mx1 > 4611686016279904256LL || mx2 > 4611686016279904256LL || mx1-mn1 > 4611686016279904256LL || mx2-mn2 > 4611686016279904256LL){
  363. sortI(N,A,B,mem);
  364. return;
  365. }
  366. r1 = (typename cLtraits_try_make_unsigned<T1>::type)(mx1) - (typename cLtraits_try_make_unsigned<T1>::type)(mn1);
  367. r2 = (typename cLtraits_try_make_unsigned<T2>::type)(mx2) - (typename cLtraits_try_make_unsigned<T2>::type)(mn2);
  368. if(r1 == 0){
  369. sortA_1_call_L(N, B, mem);
  370. return;
  371. }
  372. if(r2 == 0){
  373. sortA_1_call_L(N, A, mem);
  374. return;
  375. }
  376. if(r1 <= N){
  377. so2 = 1;
  378. for(i=(1);i<(N);i++){
  379. if(B[i-1] > B[i]){
  380. so2 = 0;
  381. break;
  382. }
  383. }
  384. if(so2 == 1){
  385. T1*aa;
  386. T2*bb;
  387. int*pos;
  388. int k;
  389. walloc1d(&aa,N,&mem);
  390. walloc1d(&bb,N,&mem);
  391. walloc1d(&pos,r1+2,&mem);
  392. for(i=(0);i<(r1+2);i++){
  393. pos[i] = 0;
  394. }
  395. for(i=(0);i<(N);i++){
  396. aa[i] = A[i];
  397. }
  398. for(i=(0);i<(N);i++){
  399. bb[i] = B[i];
  400. }
  401. for(i=(0);i<(N);i++){
  402. pos[(typename cLtraits_try_make_unsigned<T1>::type)((typename cLtraits_try_make_unsigned<T1>::type)aa[i]-(typename cLtraits_try_make_unsigned<T1>::type)mn1)+1]++;
  403. }
  404. for(i=(1);i<(r1+2);i++){
  405. pos[i] += pos[i-1];
  406. }
  407. for(i=(0);i<(N);i++){
  408. k = pos[(typename cLtraits_try_make_unsigned<T1>::type)((typename cLtraits_try_make_unsigned<T1>::type)aa[i]-(typename cLtraits_try_make_unsigned<T1>::type)mn1)+0]++;
  409. A[k] = aa[i];
  410. B[k] = bb[i];
  411. }
  412. return;
  413. }
  414. }
  415. s1 = s2 = 1;
  416. while( s1 < 64 && r1 >= (1ULL<<s1) ){
  417. s1++;
  418. }
  419. while( s2 < 64 && r2 >= (1ULL<<s2) ){
  420. s2++;
  421. }
  422. if(s1 + s2 <= 32){
  423. unsigned*tmp;
  424. walloc1d(&tmp,N,&mem);
  425. for(i=(0);i<(N);i++){
  426. tmp[i] = (((unsigned)((int)A[i]-(int)mn1)) << s2) | ((unsigned)((int)B[i]-(int)mn2));
  427. }
  428. sortA_1_call_L(N, tmp, mem);
  429. for(i=(0);i<(N);i++){
  430. A[i] = ((int)(tmp[i] >> s2)) + ((int)mn1);
  431. B[i] = ((int)(tmp[i] & ((1U<<s2)-1))) + ((int)mn2);
  432. }
  433. return;
  434. }
  435. if(s1 + s2 <= 64){
  436. unsigned long long*tmp;
  437. walloc1d(&tmp,N,&mem);
  438. for(i=(0);i<(N);i++){
  439. tmp[i] = (((unsigned long long)((long long)A[i]-(long long)mn1)) << s2) | ((unsigned long long)((long long)B[i]-(long long)mn2));
  440. }
  441. sortA_1_call_L(N, tmp, mem);
  442. for(i=(0);i<(N);i++){
  443. A[i] = ((long long)(tmp[i] >> s2)) + ((long long)mn1);
  444. B[i] = ((long long)(tmp[i] & ((1ULL<<s2)-1))) + ((long long)mn2);
  445. }
  446. return;
  447. }
  448. sortI(N,A,B,mem);
  449. }
  450. template<class T1, class T2> void sortA_2_nonint_L(int N, T1 A[], T2 B[], void *mem = wmem){
  451. sortI(N,A,B,mem);
  452. }
  453. template<class T1, class T2> void sortA_2_call_L(int N, T1 A[], T2 B[], void *mem = wmem){
  454. sortA_2_nonint_L(N, A, B, mem);
  455. }
  456. template<class T2> void sortA_2_call_L(int N, int A[], T2 B[], void *mem){
  457. sortA_2_int_L(N, A, B, mem);
  458. }
  459. template<class T2> void sortA_2_call_L(int N, unsigned A[], T2 B[], void *mem){
  460. sortA_2_int_L(N, A, B, mem);
  461. }
  462. template<class T2> void sortA_2_call_L(int N, long long A[], T2 B[], void *mem){
  463. sortA_2_int_L(N, A, B, mem);
  464. }
  465. template<class T2> void sortA_2_call_L(int N, unsigned long long A[], T2 B[], void *mem){
  466. sortA_2_int_L(N, A, B, mem);
  467. }
  468. template<class T2> void sortA_2_call_L(int N, char A[], T2 B[], void *mem){
  469. sortA_2_int_L(N, A, B, mem);
  470. }
  471. template<class T1, class T2> void sortA(int N, T1 a[], T2 b[], void *mem = wmem){
  472. sortA_2_call_L(N, a, b, mem);
  473. }
  474. template<class T1, class T2, class T3> void sortA(int N, T1 a[], T2 b[], T3 c[], void *mem = wmem){
  475. int i;
  476. pair<T1, pair<T2, T3> >*arr;
  477. walloc1d(&arr, N, &mem);
  478. for(i=(0);i<(N);i++){
  479. arr[i].first = a[i];
  480. arr[i].second.first = b[i];
  481. arr[i].second.second = c[i];
  482. }
  483. sort(arr, arr+N);
  484. for(i=(0);i<(N);i++){
  485. a[i] = arr[i].first;
  486. b[i] = arr[i].second.first;
  487. c[i] = arr[i].second.second;
  488. }
  489. }
  490. template<class T1, class T2, class T3, class T4> void sortA(int N, T1 a[], T2 b[], T3 c[], T4 d[], void *mem = wmem){
  491. int i;
  492. pair<pair<T1, T2>, pair<T3, T4> >*arr;
  493. walloc1d(&arr, N, &mem);
  494. for(i=(0);i<(N);i++){
  495. arr[i].first.first = a[i];
  496. arr[i].first.second = b[i];
  497. arr[i].second.first = c[i];
  498. arr[i].second.second = d[i];
  499. }
  500. sort(arr, arr+N);
  501. for(i=(0);i<(N);i++){
  502. a[i] = arr[i].first.first;
  503. b[i] = arr[i].first.second;
  504. c[i] = arr[i].second.first;
  505. d[i] = arr[i].second.second;
  506. }
  507. }
  508. template<class T> void Unique(int &N, T A[], int sorted=0, void *mwm = wmem){
  509. int i;
  510. int k;
  511. if(!sorted){
  512. sortA(N, A);
  513. }
  514. k = 0;
  515. for(i=(0);i<(N);i++){
  516. if(k==0 || A[k-1]!=A[i]){
  517. A[k++] = A[i];
  518. }
  519. }
  520. N = k;
  521. }
  522. template<class T, class S> void Unique(int &N, T A[], S B[], int sorted=0, void *mem = wmem){
  523. int i;
  524. int k = 0;
  525. if(!sorted){
  526. sortA(N, A, B, mem);
  527. }
  528. for(i=(0);i<(N);i++){
  529. if(!k || A[k-1]!=A[i]){
  530. A[k] = A[i];
  531. B[k] = B[i];
  532. k++;
  533. }
  534. else{
  535. B[k-1] += B[i];
  536. }
  537. }
  538. N=k;
  539. }
  540. #define main dummy_main
  541. int main(){
  542. wmem = memarr;
  543. return 0;
  544. }
  545. #undef main
  546. int N;
  547. int A[1000000];
  548. int B[1000000];
  549. long long ok[1000000];
  550. long long val[1000000];
  551. long long x[1000000];
  552. long long y[1000000];
  553. class Solution{
  554. public:
  555. int minGroupsForValidAssignment(vector<int> &nums){
  556. dummy_main();
  557. int i;
  558. int j;
  559. int k;
  560. int M = nums.size();
  561. long long res = 4611686016279904256LL;
  562. N = nums.size();
  563. for(i=(0);i<(N);i++){
  564. A[i] = nums[i];
  565. B[i] = 1;
  566. }
  567. Unique(N, A, B);
  568. for(i=(0);i<(M+1);i++){
  569. ok[i] = val[i] = 0;
  570. }
  571. for(i=(0);i<(N);i++){
  572. for(j=(0);j<(B[i]+1);j++){
  573. x[j] = 0;
  574. y[j] = 1073709056;
  575. }
  576. for(j=(1);j<(B[i]+1);j++){
  577. k = B[i] / j;
  578. x[k] = 1;
  579. chmin(y[k], j);
  580. if(B[i]%j==0){
  581. x[k-1] = 1;
  582. chmin(y[k-1], j);
  583. }
  584. }
  585. for(j=(0);j<(B[i]+1);j++){
  586. ok[j] += x[j];
  587. val[j] += y[j];
  588. }
  589. }
  590. for(i=(1);i<(M+1);i++){
  591. if(ok[i]==N){
  592. chmin(res, val[i]);
  593. }
  594. }
  595. return res;
  596. }
  597. }
  598. ;
  599. // cLay version 20231031-1
  600.  
  601. // --- original code ---
  602. // #define main dummy_main
  603. // {}
  604. // #undef main
  605. //
  606. // int N, A[1d6], B[];
  607. // ll ok[], val[], x[], y[];
  608. //
  609. // class Solution {
  610. // public:
  611. // int minGroupsForValidAssignment(VI &nums) {
  612. // dummy_main();
  613. // int i, j, k, M = nums.size();
  614. // ll res = ll_inf;
  615. // N = nums.size();
  616. // rep(i,N) A[i] = nums[i], B[i] = 1;
  617. // Unique(N, A, B);
  618. //
  619. // rep(i,M+1) ok[i] = val[i] = 0;
  620. // rep(i,N){
  621. // rep(j,B[i]+1) x[j] = 0, y[j] = int_inf;
  622. // rep(j,1,B[i]+1){
  623. // k = B[i] / j;
  624. // x[k] = 1;
  625. // y[k] <?= j;
  626. // if(B[i]%j==0) x[k-1] = 1, y[k-1] <?= j;
  627. // }
  628. // rep(j,B[i]+1) ok[j] += x[j], val[j] += y[j];
  629. // }
  630. //
  631. // rep(i,1,M+1) if(ok[i]==N) res <?= val[i];
  632. // return res;
  633. // }
  634. // };
  635.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
Standard output is empty