oj.uz

Submission #64402

# Submission time Handle Problem Language Result Execution time Memory
64402 2018-08-04T09:58:05 Z Talant Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 441 ms 7124 KB 
#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define Scan(a) scanf ("%I64d", &a)
#define scan(a) scanf ("%d", &a)

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)2e6 + 7;

int n,k;
int a[N];
int ind = 1,c;

deque <int> q;
vector <pair<int,int> > vec;

main () {
      cin >> n >> k;

      for (int i = 1; i <= n; i ++)
            cin >> a[i];

      q.pb(30);

      while (ind <= n) {
            if (q.front() == a[ind]) {
                  q.pop_front();
                  ind ++;
            }
            else {
                  if (q.front() > a[ind]) {
                        int o = q.front();
                        o --;
                        q.pop_front();
                        if (o >= 0) q.push_front(o),q.push_front(o);
                  }
                  else {
                        vec.pb(mk(ind,q.front()));
                        q.pop_front();
                  }
            }
      }
      for (int i = 0; i < q.size(); i ++)
            vec.pb(mk(ind ++,q[i]));

      int cur = k - (int)vec.size();
      int last = 1;

      for (auto to : vec) {
            for (int i = last; i < min(n + 1,to.fr); i ++) {
                  cout << a[i] << " ";
                  c ++;
            }
            q.clear();
            q.push_back(to.sc);
            deque<int> d;

            while (cur > 0 && !q.empty()) {
                  int o = q.front();
                  o --;
                  q.pop_front();
                  if (o >= 0) q.push_front(o),q.push_front(o),cur --;
                  else d.pb(o + 1);
            }
            for (auto to : d) {
                  cout << to << " ";
                  c ++;
            }
            for (auto to : q) {
                  c ++;
                  cout << to << " ";
            }
            last = to.fr;
      }
      for (int i = last; i <= n; i ++) {
            cout << a[i] << " ";
            c ++;
      }
      if (c != n + k) assert(0);
}

Compilation message

zalmoxis.cpp:24:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:50:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < q.size(); i ++)
                       ~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 6444 KB Output is correct
2 Correct 441 ms 6484 KB Output is correct
3 Correct 321 ms 6500 KB Output is correct
4 Correct 299 ms 6624 KB Output is correct
5 Correct 345 ms 6624 KB Output is correct
6 Correct 348 ms 6624 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 6624 KB Output is correct
2 Correct 394 ms 6700 KB Output is correct
3 Correct 314 ms 6700 KB Output is correct
4 Correct 360 ms 6700 KB Output is correct
5 Correct 307 ms 6700 KB Output is correct
6 Correct 387 ms 6700 KB Output is correct
7 Correct 295 ms 6700 KB Output is correct
8 Correct 342 ms 6700 KB Output is correct
9 Correct 371 ms 7124 KB Output is correct
10 Correct 225 ms 7124 KB Output is correct
11 Correct 279 ms 7124 KB Output is correct
12 Correct 138 ms 7124 KB Output is correct
13 Correct 128 ms 7124 KB Output is correct
14 Correct 128 ms 7124 KB Output is correct