fork download
copy 
  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. inline int my_getchar_unlocked(){
  7.   static char buf[1048576];
  8.   static int s = 1048576;
  9.   static int e = 1048576;
  10.   if(s == e && e == 1048576){
  11.     e = fread_unlocked(buf, 1, 1048576, stdin);
  12.     s = 0;
  13.   }
  14.   if(s == e){
  15.     return EOF;
  16.   }
  17.   return buf[s++];
  18. }
  19. inline void rd(int &x){
  20.   int k;
  21.   int m=0;
  22.   x=0;
  23.   for(;;){
  24.     k = my_getchar_unlocked();
  25.     if(k=='-'){
  26.       m=1;
  27.       break;
  28.     }
  29.     if('0'<=k&&k<='9'){
  30.       x=k-'0';
  31.       break;
  32.     }
  33.   }
  34.   for(;;){
  35.     k = my_getchar_unlocked();
  36.     if(k<'0'||k>'9'){
  37.       break;
  38.     }
  39.     x=x*10+k-'0';
  40.   }
  41.   if(m){
  42.     x=-x;
  43.   }
  44. }
  45. inline void rd(char &c){
  46.   int i;
  47.   for(;;){
  48.     i = my_getchar_unlocked();
  49.     if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
  50.       break;
  51.     }
  52.   }
  53.   c = i;
  54. }
  55. inline int rd(char c[]){
  56.   int i;
  57.   int sz = 0;
  58.   for(;;){
  59.     i = my_getchar_unlocked();
  60.     if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
  61.       break;
  62.     }
  63.   }
  64.   c[sz++] = i;
  65.   for(;;){
  66.     i = my_getchar_unlocked();
  67.     if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
  68.       break;
  69.     }
  70.     c[sz++] = i;
  71.   }
  72.   c[sz]='\0';
  73.   return sz;
  74. }
  75. inline int rd_int(void){
  76.   int x;
  77.   rd(x);
  78.   return x;
  79. }
  80. struct MY_WRITER{
  81.   char buf[1048576];
  82.   int s;
  83.   int e;
  84.   MY_WRITER(){
  85.     s = 0;
  86.     e = 1048576;
  87.   }
  88.   ~MY_WRITER(){
  89.     if(s){
  90.       fwrite_unlocked(buf, 1, s, stdout);
  91.     }
  92.   }
  93. }
  94. ;
  95. MY_WRITER MY_WRITER_VAR;
  96. void my_putchar_unlocked(int a){
  97.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  98.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  99.     MY_WRITER_VAR.s = 0;
  100.   }
  101.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  102. }
  103. inline void wt_L(char a){
  104.   my_putchar_unlocked(a);
  105. }
  106. inline void wt_L(int x){
  107.   int s=0;
  108.   int m=0;
  109.   char f[10];
  110.   if(x<0){
  111.     m=1;
  112.     x=-x;
  113.   }
  114.   while(x){
  115.     f[s++]=x%10;
  116.     x/=10;
  117.   }
  118.   if(!s){
  119.     f[s++]=0;
  120.   }
  121.   if(m){
  122.     my_putchar_unlocked('-');
  123.   }
  124.   while(s--){
  125.     my_putchar_unlocked(f[s]+'0');
  126.   }
  127. }
  128. inline void wt_L(long long x){
  129.   int s=0;
  130.   int m=0;
  131.   char f[20];
  132.   if(x<0){
  133.     m=1;
  134.     x=-x;
  135.   }
  136.   while(x){
  137.     f[s++]=x%10;
  138.     x/=10;
  139.   }
  140.   if(!s){
  141.     f[s++]=0;
  142.   }
  143.   if(m){
  144.     my_putchar_unlocked('-');
  145.   }
  146.   while(s--){
  147.     my_putchar_unlocked(f[s]+'0');
  148.   }
  149. }
  150. inline void wt_L(__int128_t x){
  151.   int s=0;
  152.   int m=0;
  153.   char f[40];
  154.   if(x<0){
  155.     m=1;
  156.     x=-x;
  157.   }
  158.   while(x){
  159.     f[s++]=x%10;
  160.     x/=10;
  161.   }
  162.   if(!s){
  163.     f[s++]=0;
  164.   }
  165.   if(m){
  166.     my_putchar_unlocked('-');
  167.   }
  168.   while(s--){
  169.     my_putchar_unlocked(f[s]+'0');
  170.   }
  171. }
  172. inline void wt_L(const char c[]){
  173.   int i=0;
  174.   for(i=0;c[i]!='\0';i++){
  175.     my_putchar_unlocked(c[i]);
  176.   }
  177. }
  178. template<class S, class T> inline S chmin(S &a, T b){
  179.   if(a>b){
  180.     a=b;
  181.   }
  182.   return a;
  183. }
  184. template<class S, class T> inline S chmax(S &a, T b){
  185.   if(a<b){
  186.     a=b;
  187.   }
  188.   return a;
  189. }
  190. int TEST;
  191. int N;
  192. char S[40];
  193. int ps;
  194. int p[20];
  195. int hist[10];
  196. int h[10];
  197. __int128_t greed(__int128_t x, __int128_t y){
  198.   int i;
  199.   for(i=(0);i<(10);i++){
  200.     h[i] = hist[i];
  201.   }
  202.   for(;;){
  203.     for(i=(0);i<(10);i++){
  204.       if(h[i]){
  205.         break;
  206.       }
  207.     }
  208.     if(i==10){
  209.       break;
  210.     }
  211.     for(i=(10)-1;i>=(0);i--){
  212.       if(h[i]){
  213.         break;
  214.       }
  215.     }
  216.     y = 10 * y + i;
  217.     h[i]--;
  218.     for(i=(0);i<(10);i++){
  219.       if(h[i]){
  220.         break;
  221.       }
  222.     }
  223.     x = 10 * x + i;
  224.     h[i]--;
  225.   }
  226.   return x - y;
  227. }
  228. int main(){
  229.   int i;
  230.   int j;
  231.   int k;
  232.   int KrdatlYV = rd_int();
  233.   for(TEST=(0);TEST<(KrdatlYV);TEST++){
  234.     __int128_t res = 4611686016279904256LL;
  235.     wt_L("Case #");
  236.     wt_L(TEST+1);
  237.     wt_L(": ");
  238.     N = rd(S);
  239.     for(i=(0);i<(10);i++){
  240.       hist[i] = 0;
  241.     }
  242.     for(i=(0);i<(N);i++){
  243.       hist[S[i]-'0']++;
  244.     }
  245.     if(N%2){
  246.       for(i=(1);i<(10);i++){
  247.         if(hist[i]){
  248.           hist[i]--;
  249.           chmin(res, greed(i,0));
  250.           hist[i]++;
  251.         }
  252.       }
  253.     }
  254.     else{
  255.       int mask;
  256.       ps = 0;
  257.       for(i=(0);i<(10);i++){
  258.         int iMWUTgY_;
  259.         for(iMWUTgY_=(0);iMWUTgY_<(hist[i]/2);iMWUTgY_++){
  260.           p[ps++] = i;
  261.         }
  262.       }
  263.       if(ps == N/2){
  264.         res = 0;
  265.       }
  266.       for(mask=(0);mask<(1<<ps);mask++){
  267.         k = -1;
  268.         for(i=(0);i<(ps);i++){
  269.           if(((mask) &(1<<(i)))){
  270.             chmax(k, p[i]);
  271.           }
  272.         }
  273.         if(k == 0){
  274.           continue;
  275.         }
  276.         for(i=(0);i<(ps);i++){
  277.           if(((mask) &(1<<(i)))){
  278.             hist[p[i]] -= 2;
  279.           }
  280.         }
  281.         for(i=(0);i<(10);i++){
  282.           if(hist[i]){
  283.             for(j=(0);j<(i);j++){
  284.               if(hist[j]){
  285.                 if(mask == 0 && j==0){
  286.                   continue;
  287.                 }
  288.                 hist[i]--;
  289.                 hist[j]--;
  290.                 chmin(res, greed(i,j));
  291.                 hist[i]++;
  292.                 hist[j]++;
  293.               }
  294.             }
  295.           }
  296.         }
  297.         for(i=(0);i<(ps);i++){
  298.           if(((mask) &(1<<(i)))){
  299.             hist[p[i]] += 2;
  300.           }
  301.         }
  302.       }
  303.     }
  304.     wt_L(res);
  305.     wt_L('\n');
  306.   }
  307.   return 0;
  308. }
  309. // cLay version 20210607-1
  310.  
  311. // --- original code ---
  312. // int TEST;
  313. // int N; char S[40];
  314. // int ps, p[20];
  315. // int hist[10], h[10];
  316. // 
  317. // __int128_t greed(__int128_t x, __int128_t y){
  318. //   rep(i,10) h[i] = hist[i];
  319. //   for(;;){
  320. //     rep(i,10) if(h[i]) break;
  321. //     if(i==10) break;
  322. // 
  323. //     rrep(i,10) if(h[i]) break;
  324. //     y = 10 * y + i; h[i]--;
  325. // 
  326. //     rep(i,10) if(h[i]) break;
  327. //     x = 10 * x + i; h[i]--;
  328. //   }
  329. //   return x - y;
  330. // }
  331. // 
  332. // {
  333. //   int i, j, k;
  334. //   REP(TEST, rd_int()){
  335. //     __int128_t res = ll_inf;
  336. //     wtF("Case #{TEST+1}: ");
  337. //     rd(S@N);
  338. //     rep(i,10) hist[i] = 0;
  339. //     rep(i,N) hist[S[i]-'0']++;
  340. // 
  341. //     if(N%2){
  342. //       rep(i,1,10) if(hist[i]){
  343. //         hist[i]--;
  344. //         res <?= greed(i,0);
  345. //         hist[i]++;
  346. //       }
  347. //     } else {
  348. //       ps = 0;
  349. //       rep(i,10) rep(hist[i]/2) p[ps++] = i;
  350. //       if(ps == N/2) res = 0;
  351. //       rep(mask, 1<<ps){
  352. //         k = -1;
  353. //         rep(i,ps) if(BIT_ith(mask,i)) k >?= p[i];
  354. //         if(k == 0) continue;
  355. //         rep(i,ps) if(BIT_ith(mask,i)) hist[p[i]] -= 2;
  356. //         rep(i,10) if(hist[i]) rep(j,i) if(hist[j]){
  357. //           if(mask == 0 && j==0) continue;
  358. //           (hist[i], hist[j])--;
  359. //           res <?= greed(i,j);
  360. //           (hist[i], hist[j])++;
  361. //         }
  362. //         rep(i,ps) if(BIT_ith(mask,i)) hist[p[i]] += 2;
  363. //       }
  364. //     }
  365. // 
  366. //     wt(res);
  367. //   }
  368. // }
  369.  
Time limit exceeded #stdin #stdout 5s 5576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mneK8v
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!