Submission #860227

#	Time	Username	Problem	Language	Result	Execution time	Memory
860227		lovrot	Teams (CEOI11_tea)	C++17	0 / 100	429 ms	38636 KiB

tea

#include <cstdio> 
#include <algorithm> 

using namespace std;

typedef long long ll; 

const int LOG = 20; 
const int N = 1 << LOG; 

int n, A[N], I[N]; 

int T[2 * N], DP[N], TO[N];

int merge(int a, int b) { return DP[a] < DP[b] ? b : a; }

void update(int x) {
	T[x + N] = x;
	for(x = (x + N) >> 1; x; x >>= 1) T[x] = merge(T[2 * x], T[2 * x + 1]);
}

int query(int l, int r, int x = 1, int lo = 0, int hi = N) {
	if(r <= lo || hi <= l) return 0;
	if(l <= lo && hi <= r) return T[x];
	int mi = (lo + hi) / 2;
	return merge(query(l, r, 2 * x, lo, mi), query(l, r, 2 * x + 1, mi, hi));
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {	
		scanf("%d", A + i); 
		I[i] = i;
	}
	sort(I, I + n + 1, [](int a, int b) { return A[a] < A[b]; });

	for(int i = 1; i <= n; ++i) {
		int res = query(0, i - A[I[i]] + 1);
		DP[i] = DP[res] + 1;
		TO[i] = res;
		update(i);
	}

	printf("%d\n", DP[n]);
	for(int i = n, j = n; i > 0; --i) {
		if(i == TO[j]) {
			printf("\n");
			j = i;
		}
		printf("%d ", I[i]);
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

tea.cpp: In function 'int main()':
tea.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
tea.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10