LeetCode Weekly Contest 151 4問目 - Dinner Plate Stacks [1172]

Source

LeetCode Weekly Contest 151
問題文

問題概要

省略

解法

省略

cLay（version 20190829-1）のコード

C++に変換後のコードはこちら

#define main dummy_main
{}
#undef main

class DinnerPlates {
public:
  int cap;
  vector<int> v[200000];
  Heap<int> canpush;
  Heap_max<int> nonempty;

  DinnerPlates(int capacity) {
    cap = capacity;
    canpush.malloc(2d5);
    nonempty.malloc(2d5);
    rep(i,2d5) canpush.push(i);
  }

  ~DinnerPlates(void){
    canpush.free();
    nonempty.free();
  }
  
  void push(int val) {
    int k;
    for(;;){
      k = canpush.pop();
      if(v[k].size() < cap) break;
    }
    v[k].push_back(val);
    if(v[k].size() == 1) nonempty.push(k);
    if(v[k].size() != cap) canpush.push(k);
  }
  
  int pop() {
    int k;
    for(;;){
      if(nonempty.size==0) return -1;
      k = nonempty.pop();
      if(v[k].size()) break;
    }
    return popAtStack(k);
  }
  
  int popAtStack(int index) {
    int res;
    if(v[index].size()==0) return -1;
    res = v[index][v[index].size()-1];
    v[index].pop_back();
    if(v[index].size() >= 1) nonempty.push(index);
    if(v[index].size() == cap-1) canpush.push(index);
    return res;
  }
};

Current time: 2024年04月26日03時54分54秒
Last modified: 2019年08月30日08時06分26秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)