oj.uz

Submission #289772

# Submission time Handle Problem Language Result Execution time Memory
289772 2020-09-03T03:52:06 Z duckmoon99 Zalmoxis (BOI18_zalmoxis) C++14
95 / 100
 400 ms 8296 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace std::chrono;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector <ii> vii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

/*
5 1
29 27 25 25 28
*/

int main(){
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	int n, k; cin >> n >> k;
	int x;
	stack<int> s, curr;
	int ans[n+k];
	int idx = n+k-1;
	for(int i = 0; i < n; i++){
		cin >> x;
		s.push(x);
	}
	curr.push(30);
	while(!s.empty()){
		if(curr.empty() || idx<=-1){
			//printf("not enough\n");
			cout << -1 << '\n';
			return 0;
		}
		//printf("curr.top:%d s.top:%d idx:%d\n",curr.top(),s.top(),idx);
		x = curr.top();
		curr.pop();
		if(x<s.top()){
			ans[idx]=x;
			idx--;
		}else if(x==s.top()){
			ans[idx]=x;
			s.pop();
			idx--;
		}else{
			curr.push(x-1);
			curr.push(x-1);
		}
	}
	while(idx>=0){
		if(curr.size()>idx+1 || curr.empty()){
			//printf("leftover");
			cout << -1 <<'\n';
			return 0;
		}else if(curr.size()==idx+1){
			ans[idx]=curr.top();
			curr.pop();
			idx--;
		}else{
			if(curr.top() == 0){
				ans[idx]=curr.top();
				curr.pop();
				idx--;
			}else{
				x=curr.top();
				curr.pop();
				curr.push(x-1);
				curr.push(x-1);
			}
		}
	}
	
	for(int i = 0; i < n+k; i++){
		cout<<ans[i]<<" ";
	}
	cout << '\n';
	
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:66:17: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |   if(curr.size()>idx+1 || curr.empty()){
      |      ~~~~~~~~~~~^~~~~~
zalmoxis.cpp:70:23: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |   }else if(curr.size()==idx+1){
      |            ~~~~~~~~~~~^~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 6740 KB Output is correct
2 Correct 394 ms 6704 KB Output is correct
3 Correct 389 ms 6588 KB Output is correct
4 Correct 396 ms 6592 KB Output is correct
5 Correct 394 ms 6756 KB Output is correct
6 Correct 391 ms 6592 KB Output is correct

Subtask #2
65.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 6820 KB Output is correct
2 Correct 399 ms 6580 KB Output is correct
3 Incorrect 296 ms 4776 KB Unexpected end of file - int32 expected
4 Correct 394 ms 6720 KB Output is correct
5 Correct 400 ms 6760 KB Output is correct
6 Correct 389 ms 6704 KB Output is correct
7 Correct 389 ms 6576 KB Output is correct
8 Correct 392 ms 6560 KB Output is correct
9 Correct 334 ms 8296 KB Output is correct
10 Correct 199 ms 7492 KB Output is correct
11 Correct 252 ms 8256 KB Output is correct
12 Correct 111 ms 6268 KB Output is correct
13 Correct 112 ms 6308 KB Output is correct
14 Correct 126 ms 6392 KB Output is correct