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. void*wmem;
  7. char memarr[96000000];
  8. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  9.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  10.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  11.   (*arr)=(T*)(*mem);
  12.   (*mem)=((*arr)+x);
  13. }
  14. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  15.   walloc1d(arr, x2-x1, mem);
  16.   (*arr) -= x1;
  17. }
  18. template<class T> inline void walloc2d(T ***arr, int x, int y, void **mem = &wmem){
  19.   int i;
  20.   walloc1d(arr, x, mem);
  21.   for(i=(0);i<(x);i++){
  22.     walloc1d(&((*arr)[i]), y, mem);
  23.   }
  24. }
  25. template<class T> inline void walloc2d(T ***arr, int x1, int x2, int y1, int y2, void **mem = &wmem){
  26.   int i;
  27.   walloc1d(arr, x1, x2, mem);
  28.   for(i=(x1);i<(x2);i++){
  29.     walloc1d(&((*arr)[i]), y1, y2, mem);
  30.   }
  31. }
  32. template<class T> T Hungarian(T **mat, int n, int m, int match[] = NULL, void *mem = wmem){
  33.   int i;
  34.   int a;
  35.   int b;
  36.   int c;
  37.   int r;
  38.   int z;
  39.   int*toright;
  40.   int*toleft;
  41.   T*ofsleft;
  42.   T*ofsright;
  43.   int*left;
  44.   int*right;
  45.   int*trace;
  46.   int*ptr;
  47.   T d;
  48.   T t;
  49.   T res = 0;
  50.   walloc1d(&toright, n, &mem);
  51.   walloc1d(&toleft, m, &mem);
  52.   walloc1d(&ofsleft, n, &mem);
  53.   walloc1d(&ofsright, m, &mem);
  54.   walloc1d(&left, n, &mem);
  55.   walloc1d(&right, m, &mem);
  56.   walloc1d(&trace, m, &mem);
  57.   walloc1d(&ptr, m, &mem);
  58.   for(i=(0);i<(n);i++){
  59.     toright[i] = -1;
  60.     ofsleft[i] = 0;
  61.   }
  62.   for(i=(0);i<(m);i++){
  63.     toleft[i] = -1;
  64.     ofsright[i] = 0;
  65.   }
  66.   for(r=(0);r<(n);r++){
  67.     for(i=(0);i<(n);i++){
  68.       left[i] = 0;
  69.     }
  70.     for(i=(0);i<(m);i++){
  71.       right[i] = 0;
  72.     }
  73.     for(i=(0);i<(m);i++){
  74.       trace[i] = -1;
  75.       ptr[i] = r;
  76.     }
  77.     left[r] = 1;
  78.     for(;;){
  79.       d = std::numeric_limits<T>::max();
  80.       for(i=(0);i<(m);i++){
  81.         if(!right[i]){
  82.           t = mat[ptr[i]][i] + ofsleft[ptr[i]] + ofsright[i];
  83.           if(d > t){
  84.             d = t;
  85.             b = i;
  86.           }
  87.         }
  88.       }
  89.       res += d;
  90.       for(i=(0);i<(n);i++){
  91.         if(left[i]){
  92.           ofsleft[i] -= d;
  93.         }
  94.       }
  95.       for(i=(0);i<(m);i++){
  96.         if(right[i]){
  97.           ofsright[i] += d;
  98.         }
  99.       }
  100.       trace[b] = ptr[b];
  101.       c = toleft[b];
  102.       if(c < 0){
  103.         while(b>=0){
  104.           a = trace[b];
  105.           z = toright[a];
  106.           toleft[b] = a;
  107.           toright[a] = b;
  108.           b = z;
  109.         }
  110.         break;
  111.       }
  112.       right[b] = left[c] = 1;
  113.       for(i=(0);i<(m);i++){
  114.         if(mat[c][i] + ofsleft[c] + ofsright[i] < mat[ptr[i]][i] + ofsleft[ptr[i]] + ofsright[i]){
  115.           ptr[i] = c;
  116.         }
  117.       }
  118.     }
  119.   }
  120.   if(match!=NULL){
  121.     for(i=(0);i<(n);i++){
  122.       match[i] = toright[i];
  123.     }
  124.   }
  125.   return res;
  126. }
  127. #define main dummy_main
  128. int main(){
  129.   wmem = memarr;
  130.   return 0;
  131. }
  132. #undef main
  133. class Solution{
  134.   public:
  135.   int minimumXORSum(vector<int>& A, vector<int>& B){
  136.     int i;
  137.     dummy_main();
  138.     int**mat;
  139.     int N = A.size();
  140.     walloc2d(&mat,N,N);
  141.     for(i=(0);i<(N);i++){
  142.       int j;
  143.       for(j=(0);j<(N);j++){
  144.         mat[i][j] = A[i] ^ B[j];
  145.       }
  146.     }
  147.     return Hungarian(mat, N, N);
  148.   }
  149. }
  150. ;
  151. // cLay version 20210607-1
  152.  
  153. // --- original code ---
  154. // #define main dummy_main
  155. // {}
  156. // #undef main
  157. // 
  158. // 
  159. // class Solution {
  160. // public:
  161. //   int minimumXORSum(vector<int>& A, vector<int>& B) {
  162. //     dummy_main();
  163. //     int **mat, N = A.size();
  164. //     walloc2d(&mat,N,N);
  165. //     rep(i,N) rep(j,N) mat[i][j] = A[i] ^ B[j];
  166. //     return Hungarian(mat, N, N);
  167. //   }
  168. // };
  169.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/6RxIHR
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!