oj.uz

Submission #64507

# Submission time Handle Problem Language Result Execution time Memory
64507 2018-08-04T17:02:57 Z mirbek01 Zalmoxis (BOI18_zalmoxis) C++17
35 / 100
 363 ms 11384 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] << " ";
      }
}

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 220 ms 6264 KB Output is correct
2 Correct 278 ms 6404 KB Output is correct
3 Correct 363 ms 6492 KB Output is correct
4 Correct 264 ms 6588 KB Output is correct
5 Correct 258 ms 6692 KB Output is correct
6 Correct 205 ms 6692 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 243 ms 6692 KB Unexpected end of file - int32 expected
2 Correct 287 ms 6692 KB Output is correct
3 Runtime error 185 ms 8616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 292 ms 10616 KB Unexpected end of file - int32 expected
5 Incorrect 262 ms 10708 KB Unexpected end of file - int32 expected
6 Incorrect 236 ms 10708 KB Unexpected end of file - int32 expected
7 Incorrect 276 ms 10752 KB Unexpected end of file - int32 expected
8 Incorrect 252 ms 10752 KB Unexpected end of file - int32 expected
9 Incorrect 232 ms 11384 KB Unexpected end of file - int32 expected
10 Incorrect 188 ms 11384 KB Unexpected end of file - int32 expected
11 Incorrect 199 ms 11384 KB Unexpected end of file - int32 expected
12 Runtime error 16 ms 11384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 17 ms 11384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 21 ms 11384 KB Execution killed with signal 11 (could be triggered by violating memory limits)