Submission #64402

#	Time	Username	Problem	Language	Result	Execution time	Memory
64402		Talant	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	441 ms	7124 KiB

zalmoxis

#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 (stderr)

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 / 30
• Subtask 2: 70 / 70