oj.uz

Submission #909793

# Submission time Handle Problem Language Result Execution time Memory
909793 2024-01-17T12:27:07 Z 8pete8 Zalmoxis (BOI18_zalmoxis) C++17
30 / 100
 1000 ms 47460 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 122 ms 20292 KB Output is correct
2 Correct 109 ms 20476 KB Output is correct
3 Correct 146 ms 20276 KB Output is correct
4 Correct 116 ms 20380 KB Output is correct
5 Correct 104 ms 20396 KB Output is correct
6 Correct 135 ms 20216 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 336 ms 27704 KB Expected EOF
2 Incorrect 181 ms 22712 KB Expected EOF
3 Incorrect 206 ms 23204 KB Expected EOF
4 Incorrect 599 ms 36292 KB Expected EOF
5 Incorrect 191 ms 23056 KB Expected EOF
6 Incorrect 281 ms 25724 KB Expected EOF
7 Incorrect 381 ms 29500 KB Expected EOF
8 Incorrect 144 ms 20236 KB Expected EOF
9 Execution timed out 1040 ms 47460 KB Time limit exceeded
10 Execution timed out 1076 ms 38420 KB Time limit exceeded
11 Execution timed out 1027 ms 40744 KB Time limit exceeded
12 Execution timed out 1086 ms 33732 KB Time limit exceeded
13 Execution timed out 1010 ms 31496 KB Time limit exceeded
14 Execution timed out 1062 ms 29824 KB Time limit exceeded