oj.uz

Submission #64786

# Submission time Handle Problem Language Result Execution time Memory
64786 2018-08-05T16:16:04 Z Good Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 334 ms 7220 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 - 1, 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 && !dq.empty()){
                        int v = dq.front();
                        dq.pop_front();
                        v --;
                        if(v >= 0){
                              dq.push_front(v);
                              dq.push_front(v);
                              k --;
                        } else
                              vv.push_back(0);
                  }
                  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: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 208 ms 6228 KB Output is correct
2 Correct 278 ms 6348 KB Output is correct
3 Correct 208 ms 6460 KB Output is correct
4 Correct 302 ms 6468 KB Output is correct
5 Correct 249 ms 6508 KB Output is correct
6 Correct 215 ms 6508 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 6508 KB Output is correct
2 Correct 257 ms 6648 KB Output is correct
3 Correct 209 ms 6676 KB Output is correct
4 Correct 210 ms 6696 KB Output is correct
5 Correct 208 ms 6696 KB Output is correct
6 Correct 319 ms 6696 KB Output is correct
7 Correct 316 ms 6804 KB Output is correct
8 Correct 296 ms 6804 KB Output is correct
9 Correct 334 ms 7220 KB Output is correct
10 Correct 222 ms 7220 KB Output is correct
11 Correct 199 ms 7220 KB Output is correct
12 Correct 108 ms 7220 KB Output is correct
13 Correct 147 ms 7220 KB Output is correct
14 Correct 139 ms 7220 KB Output is correct