Submission #255201

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
255201	2020-07-31T14:14:19 Z	Saboon	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	502 ms	257016 KB

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

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.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	467 ms	256936 KB	Output is correct
2	Correct	486 ms	256904 KB	Output is correct
3	Correct	482 ms	256888 KB	Output is correct
4	Correct	494 ms	256888 KB	Output is correct
5	Correct	486 ms	257004 KB	Output is correct
6	Correct	476 ms	256760 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	502 ms	256880 KB	Output is correct
2	Correct	499 ms	256700 KB	Output is correct
3	Correct	495 ms	256632 KB	Output is correct
4	Correct	492 ms	256912 KB	Output is correct
5	Correct	479 ms	256900 KB	Output is correct
6	Correct	481 ms	257016 KB	Output is correct
7	Correct	490 ms	256888 KB	Output is correct
8	Correct	475 ms	256888 KB	Output is correct
9	Correct	408 ms	233464 KB	Output is correct
10	Correct	278 ms	187556 KB	Output is correct
11	Correct	345 ms	204792 KB	Output is correct
12	Correct	195 ms	164856 KB	Output is correct
13	Correct	194 ms	164856 KB	Output is correct
14	Correct	198 ms	164856 KB	Output is correct