oj.uz

Submission #64510

# Submission time Handle Problem Language Result Execution time Memory
64510 2018-08-04T17:11:57 Z mirbek01 Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 388 ms 7248 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] << " ";
            }
      }
      while(pos < vec.size()){
            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: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 256 ms 6264 KB Output is correct
2 Correct 286 ms 6388 KB Output is correct
3 Correct 256 ms 6508 KB Output is correct
4 Correct 240 ms 6632 KB Output is correct
5 Correct 280 ms 6632 KB Output is correct
6 Correct 388 ms 6632 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 6632 KB Output is correct
2 Correct 210 ms 6632 KB Output is correct
3 Correct 271 ms 6832 KB Output is correct
4 Correct 315 ms 6832 KB Output is correct
5 Correct 339 ms 6832 KB Output is correct
6 Correct 332 ms 6832 KB Output is correct
7 Correct 239 ms 6832 KB Output is correct
8 Correct 245 ms 6832 KB Output is correct
9 Correct 257 ms 7248 KB Output is correct
10 Correct 223 ms 7248 KB Output is correct
11 Correct 273 ms 7248 KB Output is correct
12 Correct 159 ms 7248 KB Output is correct
13 Correct 142 ms 7248 KB Output is correct
14 Correct 107 ms 7248 KB Output is correct