Submission #74134

#	Time	Username	Problem	Language	Result	Execution time	Memory
74134		jiajunlee	Zalmoxis (BOI18_zalmoxis)	C++14	0 / 100	1092 ms	141596 KiB

zalmoxis

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cmath>
#include <set>

using namespace std;

typedef long long LL;

const LL MAXN = 1000050;

LL n, k;
LL input[MAXN] = {};
vector<LL> extra[MAXN];
multiset<pair<LL, LL> > Zal;
set<LL> inde;
set<LL>::iterator ii, jj;

int main(void) 
{
  cin >> n >> k;
  for(int i0 = 0; i0 < n; i0++)
  {
    cin >> input[i0];
    Zal.insert(make_pair(input[i0], i0));
    inde.insert(i0);
  }
  while(Zal.begin()->first != 30)
  {
    LL x = Zal.begin()->first, i = Zal.begin()->second;
    //cout << x << "-" << i << " ";
    Zal.erase(Zal.begin());
    LL y = Zal.begin()->first, j = Zal.begin()->second;
    ii = inde.find(i), jj = inde.find(j);
    jj--;
    if(x == y && ii == jj)
    {
      //cout << "Combine" << endl;
      Zal.erase(Zal.begin());
      inde.erase(ii);
      Zal.insert(make_pair(x+1, j));
    }else
    {
      //cout << "Extra" << endl;
      k--;
      extra[i].push_back(x);
      Zal.insert(make_pair(x+1, i));
    }
  }
  //cout << k << endl;
  for(LL i = 0; i < n; i++)
  {
    cout << input[i] << " ";
    //cout << "Ya" << endl;
    LL num_Bro = extra[i].size();
    LL idx = 0;
    stack<LL> st;
    for(LL idx = num_Bro-1; idx >= 0; idx--)
    {
      //cout << "Ya" << endl;
      st.push(extra[i][idx]);
    }
    while(!st.empty() && k > 0)
    {
      LL x = st.top();
      st.pop();
      LL MAX = pow(2, x-1);
      if(MAX <= k)
      {
        for(LL i0 = 0; i0 < MAX; i0++)cout << 1 << " ";
        k -= MAX;
      }else
      {
        st.push(x-1);
        st.push(x-1);
        k--;
      }
      /****
      if(x == 1)cout << 1 << " ";
      else
      {
        st.push(x-1);
        st.push(x-1);
        k--;
      }  
      ****/
    }
    while(!st.empty())
    {
      cout << st.top() << " ";
      st.pop();
    }
    //cout << endl;
  }
  
  return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:58:8: warning: unused variable 'idx' [-Wunused-variable]
     LL idx = 0;
        ^~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70