oj.uz

답안 #909802

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
909802 2024-01-17T12:38:47 Z 8pete8 Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 125 ms 30656 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<float.h>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,ll>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
using namespace std;
#define int long long
#define double long double
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
const int mod=1e9+7,mxn=3e5,lg=30,inf=1e18,minf=-1e9,Mxn=100000;
int n,m;
int32_t main(){
    fastio
    cin>>n>>m;
    vector<int>v(n),ans;
    for(int i=0;i<n;i++)cin>>v[i];
    deque<int>dq;
    dq.pb(30);
    for(int i=0;i<n;i++){
        while(!dq.empty()&&dq.front()<v[i]){
            ans.pb(dq.front());
            dq.pop_front();
        }
        int k=dq.front();
        dq.pop_front();
        for(int j=k;j>v[i];j--)dq.push_front(j-1);
        ans.pb(v[i]);
    }
    while(!dq.empty()){
        ans.pb(dq.front());
        dq.pop_front();
    }
    int cur=0,tmp=0,k=m;
    m-=(ans.size()-n);
    vector<int>ra;
    for(int i=0;i<ans.size();i++){
        if(cur<n&&v[cur]==ans[i]){
            cur++;
            ra.pb(ans[i]);
            continue;
        }
        stack<int>st;
        st.push(ans[i]);
        while(!st.empty()&&st.size()-1<m){
            while(!st.empty()&&st.top()==0){
                ra.pb(0);
                m--;
                st.pop();
            }
            if(st.empty())break;
            tmp=st.top();
            st.pop();
            st.push(tmp-1);
            st.push(tmp-1);
        }
        m-=(st.size()-1);
        while(!st.empty()){
            ra.pb(st.top());
            st.pop();
        }
    }
    if(ra.size()!=n+k)assert(0);
    for(auto i:ra)cout<<i<<" ";
}

Compilation message

zalmoxis.cpp: In function 'int32_t main()':
zalmoxis.cpp:63:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=0;i<ans.size();i++){
      |                 ~^~~~~~~~~~~
zalmoxis.cpp:71:39: warning: comparison of integer expressions of different signedness: 'std::stack<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   71 |         while(!st.empty()&&st.size()-1<m){
      |                            ~~~~~~~~~~~^~
zalmoxis.cpp:89:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   89 |     if(ra.size()!=n+k)assert(0);
      |        ~~~~~~~~~^~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 29884 KB Output is correct
2 Correct 105 ms 29632 KB Output is correct
3 Correct 116 ms 28612 KB Output is correct
4 Correct 104 ms 28448 KB Output is correct
5 Correct 106 ms 30008 KB Output is correct
6 Correct 116 ms 28356 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 29884 KB Output is correct
2 Correct 107 ms 28488 KB Output is correct
3 Correct 110 ms 29816 KB Output is correct
4 Correct 125 ms 28952 KB Output is correct
5 Correct 105 ms 28616 KB Output is correct
6 Correct 117 ms 28632 KB Output is correct
7 Correct 112 ms 29888 KB Output is correct
8 Correct 117 ms 30656 KB Output is correct
9 Correct 116 ms 27588 KB Output is correct
10 Correct 88 ms 16856 KB Output is correct
11 Correct 99 ms 23276 KB Output is correct
12 Correct 80 ms 10328 KB Output is correct
13 Correct 61 ms 10408 KB Output is correct
14 Correct 62 ms 10416 KB Output is correct