oj.uz

Submission #74134

# Submission time Handle Problem Language Result Execution time Memory
74134 2018-08-30T09:18:57 Z jiajunlee Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 1000 ms 141596 KB 
#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

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 141432 KB Time limit exceeded
2 Execution timed out 1083 ms 141432 KB Time limit exceeded
3 Execution timed out 1088 ms 141496 KB Time limit exceeded
4 Execution timed out 1089 ms 141496 KB Time limit exceeded
5 Execution timed out 1083 ms 141496 KB Time limit exceeded
6 Execution timed out 1080 ms 141496 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 141496 KB Time limit exceeded
2 Execution timed out 1092 ms 141496 KB Time limit exceeded
3 Execution timed out 1089 ms 141496 KB Time limit exceeded
4 Execution timed out 1089 ms 141496 KB Time limit exceeded
5 Execution timed out 1084 ms 141496 KB Time limit exceeded
6 Execution timed out 1090 ms 141528 KB Time limit exceeded
7 Execution timed out 1079 ms 141596 KB Time limit exceeded
8 Execution timed out 1086 ms 141596 KB Time limit exceeded
9 Execution timed out 1087 ms 141596 KB Time limit exceeded
10 Incorrect 773 ms 141596 KB Unexpected end of file - int32 expected
11 Execution timed out 1071 ms 141596 KB Time limit exceeded
12 Incorrect 106 ms 141596 KB Unexpected end of file - int32 expected
13 Incorrect 105 ms 141596 KB Unexpected end of file - int32 expected
14 Incorrect 104 ms 141596 KB Unexpected end of file - int32 expected