oj.uz

Submission #74132

# Submission time Handle Problem Language Result Execution time Memory
74132 2018-08-30T09:09:12 Z jiajunlee Zalmoxis (BOI18_zalmoxis) C++14
20 / 100
 1000 ms 170352 KB 
#include <iostream>
#include <vector>
#include <stack>
#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();
      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:56: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 1085 ms 143364 KB Time limit exceeded
2 Execution timed out 1088 ms 145656 KB Time limit exceeded
3 Execution timed out 1084 ms 147720 KB Time limit exceeded
4 Execution timed out 1085 ms 149816 KB Time limit exceeded
5 Execution timed out 1083 ms 151740 KB Time limit exceeded
6 Execution timed out 1091 ms 153704 KB Time limit exceeded

Subtask #2
20.0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 155860 KB Time limit exceeded
2 Execution timed out 1090 ms 157932 KB Time limit exceeded
3 Execution timed out 1079 ms 159712 KB Time limit exceeded
4 Execution timed out 1079 ms 162132 KB Time limit exceeded
5 Execution timed out 1095 ms 164232 KB Time limit exceeded
6 Execution timed out 1091 ms 166240 KB Time limit exceeded
7 Execution timed out 1082 ms 168204 KB Time limit exceeded
8 Execution timed out 1092 ms 170352 KB Time limit exceeded
9 Execution timed out 1084 ms 170352 KB Time limit exceeded
10 Correct 790 ms 170352 KB Output is correct
11 Execution timed out 1079 ms 170352 KB Time limit exceeded
12 Correct 144 ms 170352 KB Output is correct
13 Correct 139 ms 170352 KB Output is correct
14 Correct 135 ms 170352 KB Output is correct