oj.uz

Submission #64508

# Submission time Handle Problem Language Result Execution time Memory
64508 2018-08-04T17:05:03 Z mirbek01 Zalmoxis (BOI18_zalmoxis) C++17
35 / 100
 291 ms 11280 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 2;

int n, k, a[N];
deque <int> dq;
vector < pair <int, int> > vec;

int main(){
      scanf("%d %d", &n, &k);

      for(int i = 1; i <= n; i ++)
            scanf("%d", &a[i]);

      dq.push_back(30);

      int id = 1;

      while(id <= n){
            int v = dq.front();
            dq.pop_front();
            if(v == a[id]){
                  id ++;
            } else if(v < a[id]){
                  vec.push_back({id - 1, v});
            } else {
                  v --;
                  if(v < 0) continue;
                  dq.push_front(v);
                  dq.push_front(v);
            }
      }

      for(int i = 0; i < dq.size(); i ++)
            vec.push_back({id, dq[i]});

      k -= vec.size();
      int pos = 0;

      for(int i = 1; i <= n; i ++){
            cout << a[i] << " ";
            while(pos < vec.size() && vec[pos].first <= i){
                  vector <int> vv;
                  dq.clear();
                  dq.push_back(vec[pos ++].second);
                  while(k > 0){
                        int v = dq.front();
                        dq.pop_front();
                        v --;
                        if(v > 0){
                              dq.push_front(v);
                              dq.push_front(v);
                        } else
                              vv.push_back(0);
                        k --;
                  }
                  for(int j = 0; j < dq.size(); j ++)
                        vv.push_back(dq[j]);
                  for(int j = 0; j < vv.size(); j ++)
                        cout << vv[j] << " ";
            }
      }
      while(pos < vec.size()){
            vector <int> vv;
            dq.clear();
            dq.push_back(vec[pos ++].second);
            while(k > 0){
                  int v = dq.front();
                  dq.pop_front();
                  v --;
                  if(v > 0){
                        dq.push_front(v);
                        dq.push_front(v);
                  } else
                        vv.push_back(0);
                  k --;
            }
            for(int j = 0; j < dq.size(); j ++)
                  vv.push_back(dq[j]);
            for(int j = 0; j < vv.size(); j ++)
                  cout << vv[j] << " ";
      }
}
/**
8 2
28 27 26 25 25 25 25 28
**/

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:36:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < dq.size(); i ++)
                      ~~^~~~~~~~~~~
zalmoxis.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(pos < vec.size() && vec[pos].first <= i){
                   ~~~~^~~~~~~~~~~~
zalmoxis.cpp:59:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int j = 0; j < dq.size(); j ++)
                                  ~~^~~~~~~~~~~
zalmoxis.cpp:61:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int j = 0; j < vv.size(); j ++)
                                  ~~^~~~~~~~~~~
zalmoxis.cpp:65:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(pos < vec.size()){
             ~~~~^~~~~~~~~~~~
zalmoxis.cpp:80:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < dq.size(); j ++)
                            ~~^~~~~~~~~~~
zalmoxis.cpp:82:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < vv.size(); j ++)
                            ~~^~~~~~~~~~~
zalmoxis.cpp:12:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &k);
       ~~~~~^~~~~~~~~~~~~~~~~
zalmoxis.cpp:15:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i]);
             ~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 6396 KB Output is correct
2 Correct 247 ms 6396 KB Output is correct
3 Correct 220 ms 6432 KB Output is correct
4 Correct 240 ms 6504 KB Output is correct
5 Correct 266 ms 6568 KB Output is correct
6 Correct 291 ms 6568 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 272 ms 6568 KB Unexpected end of file - int32 expected
2 Correct 287 ms 6608 KB Output is correct
3 Runtime error 157 ms 8540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 233 ms 10628 KB Unexpected end of file - int32 expected
5 Incorrect 205 ms 10812 KB Unexpected end of file - int32 expected
6 Incorrect 227 ms 10812 KB Unexpected end of file - int32 expected
7 Incorrect 246 ms 10812 KB Unexpected end of file - int32 expected
8 Incorrect 272 ms 10816 KB Unexpected end of file - int32 expected
9 Incorrect 235 ms 11280 KB Unexpected end of file - int32 expected
10 Incorrect 148 ms 11280 KB Unexpected end of file - int32 expected
11 Incorrect 195 ms 11280 KB Unexpected end of file - int32 expected
12 Runtime error 22 ms 11280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 17 ms 11280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 19 ms 11280 KB Execution killed with signal 11 (could be triggered by violating memory limits)