oj.uz

Submission #289770

# Submission time Handle Problem Language Result Execution time Memory
289770 2020-09-03T03:48:09 Z duckmoon99 Zalmoxis (BOI18_zalmoxis) C++14
95 / 100
 399 ms 10088 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;
			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;
			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++){
		printf("%d ", ans[i]);
	}
	
}

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 8624 KB Output is correct
2 Correct 398 ms 8644 KB Output is correct
3 Correct 395 ms 8672 KB Output is correct
4 Correct 397 ms 8768 KB Output is correct
5 Correct 399 ms 8624 KB Output is correct
6 Correct 391 ms 8728 KB Output is correct

Subtask #2
65.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 8660 KB Output is correct
2 Correct 395 ms 8716 KB Output is correct
3 Incorrect 289 ms 6976 KB Unexpected end of file - int32 expected
4 Correct 391 ms 8772 KB Output is correct
5 Correct 390 ms 8804 KB Output is correct
6 Correct 389 ms 8624 KB Output is correct
7 Correct 386 ms 8752 KB Output is correct
8 Correct 398 ms 8752 KB Output is correct
9 Correct 344 ms 10088 KB Output is correct
10 Correct 198 ms 8004 KB Output is correct
11 Correct 257 ms 9384 KB Output is correct
12 Correct 115 ms 6264 KB Output is correct
13 Correct 115 ms 6264 KB Output is correct
14 Correct 112 ms 6264 KB Output is correct