fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. void*wmem;
  5. char memarr[96000000];
  6. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  7.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  8.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  9.   (*arr)=(T*)(*mem);
  10.   (*mem)=((*arr)+x);
  11. }
  12. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  13.   walloc1d(arr, x2-x1, mem);
  14.   (*arr) -= x1;
  15. }
  16. void sortF_L(int N, unsigned A[], void *mem = wmem){
  17.   int i;
  18.   int m;
  19.   int bt;
  20.   unsigned*arr;
  21.   unsigned c;
  22.   int*sz;
  23.   if(N < 256){
  24.     sort(A, A+N);
  25.     return;
  26.   }
  27.   bt = sizeof(unsigned) * 8;
  28.   walloc1d(&arr, N, &mem);
  29.   walloc1d(&sz, N, &mem);
  30.   for(m=0;m<bt;m+=8){
  31.     for(i=(0);i<(257);i++){
  32.       sz[i] = 0;
  33.     }
  34.     for(i=(0);i<(N);i++){
  35.       sz[ 1+((A[i]>>m)&255u) ]++;
  36.     }
  37.     for(i=(1);i<(257);i++){
  38.       sz[i] += sz[i-1];
  39.     }
  40.     for(i=(0);i<(N);i++){
  41.       c = ((A[i]>>m)&255u);
  42.       arr[sz[c]++] = A[i];
  43.     }
  44.     swap(A, arr);
  45.   }
  46. }
  47. void sortF_L(int N, int A[], void *mem = wmem){
  48.   int i;
  49.   int x;
  50.   int y;
  51.   int z;
  52.   int*arr;
  53.   unsigned*send;
  54.   if(N < 256){
  55.     sort(A, A+N);
  56.     return;
  57.   }
  58.   send = (unsigned*)A;
  59.   sortF_L(N, send, mem);
  60.   if(A[0] < 0 || A[N-1] >= 0){
  61.     return;
  62.   }
  63.   x = 0;
  64.   y = N;
  65.   while(x < y){
  66.     z = (x+y) / 2;
  67.     if(A[z] < 0){
  68.       y = z;
  69.     }
  70.     else{
  71.       x = z+1;
  72.     }
  73.   }
  74.   walloc1d(&arr, N, &mem);
  75.   z = 0;
  76.   for(i=(x);i<(N);i++){
  77.     arr[z++] = A[i];
  78.   }
  79.   for(i=(0);i<(x);i++){
  80.     arr[z++] = A[i];
  81.   }
  82.   for(i=(0);i<(N);i++){
  83.     A[i] = arr[i];
  84.   }
  85. }
  86. void sortF_L(int N, unsigned long long A[], void *mem = wmem){
  87.   int i;
  88.   int m;
  89.   int bt;
  90.   unsigned long long*arr;
  91.   unsigned c;
  92.   int*sz;
  93.   if(N < 512){
  94.     sort(A, A+N);
  95.     return;
  96.   }
  97.   bt = sizeof(unsigned long long) * 8;
  98.   walloc1d(&arr, N, &mem);
  99.   walloc1d(&sz, N, &mem);
  100.   for(m=0;m<bt;m+=8){
  101.     for(i=(0);i<(257);i++){
  102.       sz[i] = 0;
  103.     }
  104.     for(i=(0);i<(N);i++){
  105.       sz[ 1+((A[i]>>m)&255u) ]++;
  106.     }
  107.     for(i=(1);i<(257);i++){
  108.       sz[i] += sz[i-1];
  109.     }
  110.     for(i=(0);i<(N);i++){
  111.       c = ((A[i]>>m)&255u);
  112.       arr[sz[c]++] = A[i];
  113.     }
  114.     swap(A, arr);
  115.   }
  116. }
  117. void sortF_L(int N, long long A[], void *mem = wmem){
  118.   int i;
  119.   int x;
  120.   int y;
  121.   int z;
  122.   long long*arr;
  123.   unsigned long long*send;
  124.   if(N < 512){
  125.     sort(A, A+N);
  126.     return;
  127.   }
  128.   send = (unsigned long long*)A;
  129.   sortF_L(N, send, mem);
  130.   if(A[0] < 0 || A[N-1] >= 0){
  131.     return;
  132.   }
  133.   x = 0;
  134.   y = N;
  135.   while(x < y){
  136.     z = (x+y) / 2;
  137.     if(A[z] < 0){
  138.       y = z;
  139.     }
  140.     else{
  141.       x = z+1;
  142.     }
  143.   }
  144.   walloc1d(&arr, N, &mem);
  145.   z = 0;
  146.   for(i=(x);i<(N);i++){
  147.     arr[z++] = A[i];
  148.   }
  149.   for(i=(0);i<(x);i++){
  150.     arr[z++] = A[i];
  151.   }
  152.   for(i=(0);i<(N);i++){
  153.     A[i] = arr[i];
  154.   }
  155. }
  156. inline int my_getchar_unlocked(){
  157.   static char buf[1048576];
  158.   static int s = 1048576;
  159.   static int e = 1048576;
  160.   if(s == e && e == 1048576){
  161.     e = fread_unlocked(buf, 1, 1048576, stdin);
  162.     s = 0;
  163.   }
  164.   if(s == e){
  165.     return EOF;
  166.   }
  167.   return buf[s++];
  168. }
  169. inline void rd(int &x){
  170.   int k;
  171.   int m=0;
  172.   x=0;
  173.   for(;;){
  174.     k = my_getchar_unlocked();
  175.     if(k=='-'){
  176.       m=1;
  177.       break;
  178.     }
  179.     if('0'<=k&&k<='9'){
  180.       x=k-'0';
  181.       break;
  182.     }
  183.   }
  184.   for(;;){
  185.     k = my_getchar_unlocked();
  186.     if(k<'0'||k>'9'){
  187.       break;
  188.     }
  189.     x=x*10+k-'0';
  190.   }
  191.   if(m){
  192.     x=-x;
  193.   }
  194. }
  195. inline int rd_int(void){
  196.   int x;
  197.   rd(x);
  198.   return x;
  199. }
  200. struct MY_WRITER{
  201.   char buf[1048576];
  202.   int s;
  203.   int e;
  204.   MY_WRITER(){
  205.     s = 0;
  206.     e = 1048576;
  207.   }
  208.   ~MY_WRITER(){
  209.     if(s){
  210.       fwrite_unlocked(buf, 1, s, stdout);
  211.     }
  212.   }
  213. }
  214. ;
  215. MY_WRITER MY_WRITER_VAR;
  216. void my_putchar_unlocked(int a){
  217.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  218.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  219.     MY_WRITER_VAR.s = 0;
  220.   }
  221.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  222. }
  223. inline void wt_L(char a){
  224.   my_putchar_unlocked(a);
  225. }
  226. inline void wt_L(int x){
  227.   int s=0;
  228.   int m=0;
  229.   char f[10];
  230.   if(x<0){
  231.     m=1;
  232.     x=-x;
  233.   }
  234.   while(x){
  235.     f[s++]=x%10;
  236.     x/=10;
  237.   }
  238.   if(!s){
  239.     f[s++]=0;
  240.   }
  241.   if(m){
  242.     my_putchar_unlocked('-');
  243.   }
  244.   while(s--){
  245.     my_putchar_unlocked(f[s]+'0');
  246.   }
  247. }
  248. inline void wt_L(long long x){
  249.   int s=0;
  250.   int m=0;
  251.   char f[20];
  252.   if(x<0){
  253.     m=1;
  254.     x=-x;
  255.   }
  256.   while(x){
  257.     f[s++]=x%10;
  258.     x/=10;
  259.   }
  260.   if(!s){
  261.     f[s++]=0;
  262.   }
  263.   if(m){
  264.     my_putchar_unlocked('-');
  265.   }
  266.   while(s--){
  267.     my_putchar_unlocked(f[s]+'0');
  268.   }
  269. }
  270. inline void wt_L(const char c[]){
  271.   int i=0;
  272.   for(i=0;c[i]!='\0';i++){
  273.     my_putchar_unlocked(c[i]);
  274.   }
  275. }
  276. int TEST;
  277. int N;
  278. int X[100000];
  279. int Y[100000];
  280. int main(){
  281.   wmem = memarr;
  282.   int Lj4PdHRW = rd_int();
  283.   for(TEST=(0);TEST<(Lj4PdHRW);TEST++){
  284.     int i;
  285.     long long res = 0;
  286.     wt_L("Case #");
  287.     wt_L(TEST+1);
  288.     wt_L(": ");
  289.     rd(N);
  290.     {
  291.       int e98WHCEY;
  292.       for(e98WHCEY=(0);e98WHCEY<(N);e98WHCEY++){
  293.         rd(X[e98WHCEY]);
  294.         rd(Y[e98WHCEY]);
  295.       }
  296.     }
  297.     sortF_L(N,X);
  298.     sortF_L(N,Y);
  299.     for(i=(0);i<(N);i++){
  300.       X[i] -= i;
  301.     }
  302.     sortF_L(N,X);
  303.     for(i=(0);i<(N);i++){
  304.       res += abs(X[i]-X[N/2]);
  305.     }
  306.     for(i=(0);i<(N);i++){
  307.       res += abs(Y[i]-Y[N/2]);
  308.     }
  309.     wt_L(res);
  310.     wt_L('\n');
  311.   }
  312.   return 0;
  313. }
  314. // cLay varsion 20201115-2
  315.  
  316. // --- original code ---
  317. // int TEST;
  318. // int N, X[1d5], Y[1d5];
  319. // {
  320. //   REP(TEST,rd_int()){
  321. //     ll res = 0;
  322. //     wtF("Case #{TEST+1}: ");
  323. //     rd(N,(X,Y)(N));
  324. //     sortF(N,X);
  325. //     sortF(N,Y);
  326. //     rep(i,N) X[i] -= i;
  327. //     sortF(N,X);
  328. //     rep(i,N) res += abs(X[i]-X[N/2]);
  329. //     rep(i,N) res += abs(Y[i]-Y[N/2]);
  330. //     wt(res);
  331. //   }
  332. // }
  333.  
Time limit exceeded #stdin #stdout 5s 4368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hq2U2N
language:
C++ (gcc 8.3)
created:
3 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!