Submission #255201

#	Time	Username	Problem	Language	Result	Execution time	Memory
255201		Saboon	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	502 ms	257016 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e6 + 10;

int a[maxn], dp[maxn][32], r[maxn][32];


int extraprint(int k, int extra){
	if (extra == 0){
		printf("%d ", k);
		return 0;
	}
	int ret = extraprint(k-1, extra-1) + 1;
	extra -= ret;
	return ret + extraprint(k-1, extra);
}

int n;

int printer(int l, int k, int extra){
	if (a[l] == k){
		printf("%d ", k);
		return 0;
	}
	if (r[l][k-1] < n and r[r[l][k-1]][k-1] != -1){
		int ret = printer(l, k-1, extra);
		ret += printer(r[l][k-1], k-1, extra-ret);
		return ret;
	}
	int ret = printer(l, k-1, extra);
	ret += extraprint(k-1, extra-ret);
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	int k;
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	memset(r, -1, sizeof r);
	for (int i = n-1; i >= 0; i--){
		dp[i][a[i]] = 0;
		r[i][a[i]] = i+1;
		for (int l = a[i]+1; l <= 30; l++){
			if (r[i][l-1] < n and r[r[i][l-1]][l-1] != -1){
				r[i][l] = r[r[i][l-1]][l-1];
				dp[i][l] = dp[i][l-1] + dp[r[i][l-1]][l-1];
			}
			else{
				r[i][l] = r[i][l-1];
				dp[i][l] = dp[i][l-1] + 1;
			}
		}
	}
	assert(dp[0][30] <= k);
	printer(0, 30, k-dp[0][30]);
	printf("\n");
}

Compilation message (stderr)

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

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70