fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. void *wmem;
  5. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  6.   static int skip[16]={0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  7.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  8.   (*arr)=(T*)(*mem);
  9.   (*mem)=((*arr)+x);
  10. }
  11. template<class T> struct Heap{
  12.   T *val;
  13.   int size;
  14.   void malloc(const int N){
  15.     val = (T*) std::malloc(N*sizeof(T));
  16.     size = 0;
  17.   }
  18.   void walloc(const int N, void **mem = &wmem){
  19.     walloc1d(&val, N, mem);
  20.     size = 0;
  21.   }
  22.   void free(){
  23.     std::free(val);
  24.   }
  25.   void init(){
  26.     size = 0;
  27.   }
  28.   void up(){
  29.     int m, n=size - 1;
  30.     while(n){
  31.       m = (n-1) / 2;
  32.       if(val[m] <= val[n]){
  33.         break;
  34.       }
  35.       swap(val[m], val[n]);
  36.       n = m;
  37.     }
  38.   }
  39.   void down(){
  40.     int m, n=0;
  41.     for(;;){
  42.       m=2*n+1;
  43.       if(m>=size){
  44.         break;
  45.       }
  46.       if(m+1<size && val[m] > val[m+1]){
  47.         m++;
  48.       }
  49.       if(val[m] >= val[n]){
  50.         break;
  51.       }
  52.       swap(val[m], val[n]);
  53.       n = m;
  54.     }
  55.   }
  56.   T top(){
  57.     return val[0];
  58.   }
  59.   T pop(){
  60.     T res=val[0];
  61.     size--;
  62.     if(size > 0){
  63.       val[0] = val[size];
  64.       down();
  65.     }
  66.     return res;
  67.   }
  68.   T push(const T x){
  69.     val[size++] = x;
  70.     up();
  71.     return x;
  72.   }
  73. }
  74. ;
  75. template<class T> struct Heap_max{
  76.   T *val;
  77.   int size;
  78.   void malloc(const int N){
  79.     val = (T*) std::malloc(N*sizeof(T));
  80.     size = 0;
  81.   }
  82.   void walloc(const int N, void **mem = &wmem){
  83.     walloc1d(&val, N, mem);
  84.     size = 0;
  85.   }
  86.   void free(){
  87.     std::free(val);
  88.   }
  89.   void init(){
  90.     size = 0;
  91.   }
  92.   void up(){
  93.     int m, n=size - 1;
  94.     while(n){
  95.       m = (n-1) / 2;
  96.       if(val[m] >= val[n]){
  97.         break;
  98.       }
  99.       swap(val[m], val[n]);
  100.       n = m;
  101.     }
  102.   }
  103.   void down(){
  104.     int m, n=0;
  105.     for(;;){
  106.       m=2*n+1;
  107.       if(m>=size){
  108.         break;
  109.       }
  110.       if(m+1<size && val[m] < val[m+1]){
  111.         m++;
  112.       }
  113.       if(val[m] <= val[n]){
  114.         break;
  115.       }
  116.       swap(val[m], val[n]);
  117.       n=m;
  118.     }
  119.   }
  120.   T top(){
  121.     return val[0];
  122.   }
  123.   T pop(){
  124.     T res=val[0];
  125.     size--;
  126.     if(size > 0){
  127.       val[0] = val[size];
  128.       down();
  129.     }
  130.     return res;
  131.   }
  132.   T push(const T x){
  133.     val[size++] = x;
  134.     up();
  135.     return x;
  136.   }
  137. }
  138. ;
  139. char memarr[96000000];
  140. #define main dummy_main
  141. int main(){
  142.   wmem = memarr;
  143.   return 0;
  144. }
  145. #undef main
  146. class DinnerPlates{
  147.   Heap<int> canpush;
  148.   Heap_max<int> nonempty;
  149.   int cap;
  150.   vector<int> v[200000];
  151.   public:
  152.   DinnerPlates(int capacity){
  153.     int i;
  154.     cap = capacity;
  155.     canpush.malloc(200000);
  156.     nonempty.malloc(200000);
  157.     for(i=0;i<(200000);i++){
  158.       canpush.push(i);
  159.     }
  160.   }
  161.   ~DinnerPlates(void){
  162.     canpush.free();
  163.     nonempty.free();
  164.   }
  165.   void push(int val){
  166.     int k;
  167.     for(;;){
  168.       k = canpush.pop();
  169.       if(v[k].size() < cap){
  170.         break;
  171.       }
  172.     }
  173.     v[k].push_back(val);
  174.     if(v[k].size() == 1){
  175.       nonempty.push(k);
  176.     }
  177.     if(v[k].size() != cap){
  178.       canpush.push(k);
  179.     }
  180.   }
  181.   int pop(){
  182.     int k;
  183.     for(;;){
  184.       if(nonempty.size==0){
  185.         return -1;
  186.       }
  187.       k = nonempty.pop();
  188.       if(v[k].size()){
  189.         break;
  190.       }
  191.     }
  192.     return popAtStack(k);
  193.   }
  194.   int popAtStack(int index){
  195.     int res;
  196.     if(v[index].size()==0){
  197.       return -1;
  198.     }
  199.     res = v[index][v[index].size()-1];
  200.     v[index].pop_back();
  201.     if(v[index].size() >= 1){
  202.       nonempty.push(index);
  203.     }
  204.     if(v[index].size() == cap-1){
  205.       canpush.push(index);
  206.     }
  207.     return res;
  208.   }
  209. }
  210. ;
  211. // cLay varsion 20190829-1
  212.  
  213. // --- original code ---
  214. // #define main dummy_main
  215. // {}
  216. // #undef main
  217. // 
  218. // class DinnerPlates {
  219. // public:
  220. //   int cap;
  221. //   vector<int> v[200000];
  222. //   Heap<int> canpush;
  223. //   Heap_max<int> nonempty;
  224. // 
  225. //   DinnerPlates(int capacity) {
  226. //     cap = capacity;
  227. //     canpush.malloc(2d5);
  228. //     nonempty.malloc(2d5);
  229. //     rep(i,2d5) canpush.push(i);
  230. //   }
  231. // 
  232. //   ~DinnerPlates(void){
  233. //     canpush.free();
  234. //     nonempty.free();
  235. //   }
  236. //   
  237. //   void push(int val) {
  238. //     int k;
  239. //     for(;;){
  240. //       k = canpush.pop();
  241. //       if(v[k].size() < cap) break;
  242. //     }
  243. //     v[k].push_back(val);
  244. //     if(v[k].size() == 1) nonempty.push(k);
  245. //     if(v[k].size() != cap) canpush.push(k);
  246. //   }
  247. //   
  248. //   int pop() {
  249. //     int k;
  250. //     for(;;){
  251. //       if(nonempty.size==0) return -1;
  252. //       k = nonempty.pop();
  253. //       if(v[k].size()) break;
  254. //     }
  255. //     return popAtStack(k);
  256. //   }
  257. //   
  258. //   int popAtStack(int index) {
  259. //     int res;
  260. //     if(v[index].size()==0) return -1;
  261. //     res = v[index][v[index].size()-1];
  262. //     v[index].pop_back();
  263. //     if(v[index].size() >= 1) nonempty.push(index);
  264. //     if(v[index].size() == cap-1) canpush.push(index);
  265. //     return res;
  266. //   }
  267. // };
  268.  
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/mJg3hb
language:
C++14 (gcc 8.3)
created:
4 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!