oj.uz

Submission #909795

# Submission time Handle Problem Language Result Execution time Memory
909795 2024-01-17T12:27:45 Z 8pete8 Zalmoxis (BOI18_zalmoxis) C++17
30 / 100
 1000 ms 47836 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;
    for(int i=0;i<ans.size();i++){
        if(cur<n&&v[cur]==ans[i]){
            cur++;
            cout<<ans[i]<<" ";
            continue;
        }
        stack<int>st;
        st.push(ans[i]);
        while(!st.empty()&&st.size()<m){
            while(!st.empty()&&st.top()==0){
                cout<<0<<" ";
                m--;
                st.pop();
            }
            if(st.empty())break;
            tmp=st.top();
            st.pop();
            st.push(tmp-1);
            st.push(tmp-1);
        }
        m-=st.size();
        while(!st.empty()){
            cout<<st.top()<<" ";
            st.pop();
        }
    }
}

Compilation message

zalmoxis.cpp: In function 'int32_t main()':
zalmoxis.cpp:61: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]
   61 |     for(int i=0;i<ans.size();i++){
      |                 ~^~~~~~~~~~~
zalmoxis.cpp:69:37: 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]
   69 |         while(!st.empty()&&st.size()<m){
      |                            ~~~~~~~~~^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 18108 KB Output is correct
2 Correct 111 ms 18136 KB Output is correct
3 Correct 111 ms 18100 KB Output is correct
4 Correct 109 ms 18112 KB Output is correct
5 Correct 109 ms 18536 KB Output is correct
6 Correct 110 ms 18604 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 317 ms 25284 KB Expected EOF
2 Incorrect 175 ms 20672 KB Expected EOF
3 Incorrect 181 ms 21176 KB Expected EOF
4 Incorrect 572 ms 34256 KB Expected EOF
5 Incorrect 183 ms 20964 KB Expected EOF
6 Incorrect 262 ms 23924 KB Expected EOF
7 Incorrect 367 ms 27072 KB Expected EOF
8 Incorrect 118 ms 18376 KB Expected EOF
9 Execution timed out 1052 ms 47836 KB Time limit exceeded
10 Execution timed out 1012 ms 39104 KB Time limit exceeded
11 Execution timed out 1050 ms 44372 KB Time limit exceeded
12 Execution timed out 1039 ms 33976 KB Time limit exceeded
13 Execution timed out 1034 ms 34752 KB Time limit exceeded
14 Execution timed out 1018 ms 34164 KB Time limit exceeded