読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

codeIQ 2685

https://codeiq.jp/q/2685

(404になっていたので説明すると,順次追加される数字に対し, それまで追加された数の集合のメジアンを求めさせる問題, だったはず)

参考にしたのはこれ↓

でもこれだと負の数に対応できないので無理やり大きい数を足して調整している.

const int N = 20001;
vector<vector<int> > T;

void init()
{
  int m = N; int cnt = 0;
  while(m > 2)
  {
    vector<int> t(m,0);
    T.push_back(t);
    m /= 2;
  }
}

int nth(int m)
{
  int index = 0, sum = 0;
  DOWN(i,T.size()-1,0)
  {
    for(int j=index*2;j<T[i].size();j++)
    {
      if(sum + T[i][j] >= m)
      {
        index = j;
        break;
      }
      sum += T[i][j];
    }
  }
  return index;
}

void solve()
{
  int cnt = 0, n;
  while(cin >> n)
  {
    cnt++; n+=3000;
    REP(i,T.size()) T[i][floor(n/(1<<i))]++;
    if(cnt%2==1)
      cout << nth(cnt/2+1)-3000 << endl;
    else
      cout << (nth(cnt/2)+nth(cnt/2+1))/2-3000 << endl;
  }
}

int main()
{
  init();
  solve();
  return 0;
}