Submission #35554024

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
template <typename T> using minPQ = priority_queue<T,vector<T>, greater<T>>; // 小根堆
int read(){int r;scanf("%d",&r);return r;}

vector<int> calc(vector<pair<int,bool>>&A,int del){ // {value, free del?}
  vector<int> ret={};
  minPQ<pair<int,int>> vi; // value,index
  int li=0;
  int ri=-1; // [li..ri] 中选择最小的一个作为剩余的头
  auto moveri=[&](int d){
    while(d>=0) {
      if(++ri>=(int)A.size())break;
      if(!A[ri].second)d--;// not free d
      vi.push({A[ri].first,ri});
    }
  };
  moveri(del);
  while(ri<(int)A.size()){
    auto [v,i]=vi.top();
    vi.pop();
    if(i<li)continue;
    // use A[i], [li...i...ri] => [i+1..ri+(1/0)]
    ret.push_back(v);
    li=i+1;
    if(!A[i].second)moveri(0);
  }
  return ret;
}

void p(const vector<int>&A){rep(i,0,A.size())printf("%d%c",A[i]," \n"[i+1==(int)A.size()]);}
int le(const vector<int>&A,const vector<int>&B){ // less equal
  int n = min(A.size(),B.size());
  rep(i,0,n)if(A[i]!=B[i]) return A[i]<B[i];
  return A.size()<B.size();
}

int main(){
  int n = read();
  vector<int>a(n);
  int k = read();
  rep(i,0,n) a[i]=read();
  if(k==0){
    p(a);
    return 0;
  }
  // left del
  int li=0;
  rep(i,0,k+1)if(a[i]<a[li])li=i;
  vector<pair<int,bool>>al={};
  rep(i,li,n)al.push_back({a[i],false});
  auto ansl=calc(al,k-li);
  // right move
  int ri=n-1;
  rep(i,0,k) if(a[n-1-i]<a[ri])ri=n-1-i;
  vector<pair<int,bool>>ar={};
  rep(i,0,n)ar.push_back({a[(ri+i)%n],ri+i<n});
  auto ansr=calc(ar,k-(n-ri));
  p(le(ansl,ansr)?ansl:ansr);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:5:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    5 | int read(){int r;scanf("%d",&r);return r;}
      |                  ~~~~~^~~~~~~~~

Judge Result