oj.uz

Submission #59904

# Submission time Handle Problem Language Result Execution time Memory
59904 2018-07-23T09:42:32 Z Kerim Zalmoxis (BOI18_zalmoxis) C++17
0 / 100
 129 ms 10680 KB 
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int arr[MAXN];
vector<int>adj[MAXN];
vector<int>vec;
void solve(int x,int y){
	vector<int>v,g;
	v.pb(x);
	while(y){
		if(!v.size()){
			swap(v,g);
			g.clear();
		}
		g.pb(v.back()-1);
		g.pb(v.back()-1);
		v.ppb();
		y--;
	}
	tr(it,v)
		printf("%d ",*it);
	tr(it,g)
		printf("%d ",*it);
}
int main(){
    //~ freopen("file.in", "r", stdin);
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
		scanf("%d",arr+i);
	stack<PII>st;	
	st.push(mp(arr[1],1));
	int cnt=0;
	for(int i=2;i<=n;i++){
		int now=arr[i],ok=0;
		while(!ok){
			while(!st.empty() and st.top().ff==now){
				st.pop();
				now++;
			}
			if(st.empty())
				st.push(mp(now,i)),ok=1;
			else{
				if(st.top().ff<now){
					while(st.top().ff<now){
						PII tmp=st.top();st.pop();
						if(st.empty() or st.top().ff!=tmp.ff)
							adj[tmp.ss].pb(tmp.ff),cnt++;
						else
							st.pop();
						st.push(mp(tmp.ff+1,tmp.ss));
					}
				}
				else
					st.push(mp(now,i)),ok=1;
			}	
		}
	}	
	while(!st.empty()){
		PII tmp=st.top();st.pop();
		if(tmp.ff==30)
			break;
		if(!st.empty() and st.top().ff==tmp.ff)
			st.pop();
		else
			adj[tmp.ss].pb(tmp.ff),cnt++;
		st.push(mp(tmp.ff+1,tmp.ss));	
	}
	assert(cnt<=k);
	k-=cnt;
	for(int i=1;i<=n;i++){
		printf("%d ",arr[i]);
		tr(it,adj[i]){
			if((1<<*it)<=k){
				k-=(1<<*it);
				for(int j=0;j<(1<<(*it));j++)
					printf("0 ");
			}
			else
				solve(*it,k),k=0;
		}
	}puts("");
	return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
zalmoxis.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",arr+i);
   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 17 ms 3064 KB Time limit exceeded (wall clock)
2 Execution timed out 23 ms 3172 KB Time limit exceeded (wall clock)
3 Execution timed out 18 ms 3228 KB Time limit exceeded (wall clock)
4 Execution timed out 16 ms 3332 KB Time limit exceeded (wall clock)
5 Execution timed out 19 ms 3332 KB Time limit exceeded (wall clock)
6 Execution timed out 16 ms 3332 KB Time limit exceeded (wall clock)

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 17 ms 3332 KB Time limit exceeded (wall clock)
2 Execution timed out 16 ms 3332 KB Time limit exceeded (wall clock)
3 Execution timed out 14 ms 3332 KB Time limit exceeded (wall clock)
4 Execution timed out 16 ms 3332 KB Time limit exceeded (wall clock)
5 Execution timed out 15 ms 3332 KB Time limit exceeded (wall clock)
6 Execution timed out 16 ms 3332 KB Time limit exceeded (wall clock)
7 Runtime error 18 ms 6116 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Execution timed out 16 ms 6208 KB Time limit exceeded (wall clock)
9 Execution timed out 16 ms 6208 KB Time limit exceeded (wall clock)
10 Runtime error 19 ms 6208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Execution timed out 15 ms 6220 KB Time limit exceeded (wall clock)
12 Incorrect 129 ms 10676 KB Unexpected end of file - int32 expected
13 Incorrect 113 ms 10676 KB Unexpected end of file - int32 expected
14 Incorrect 115 ms 10680 KB Unexpected end of file - int32 expected