oj.uz

Submission #860230

# Submission time Handle Problem Language Result Execution time Memory
860230 2023-10-12T09:20:32 Z lovrot Teams (CEOI11_tea) C++17
0 / 100
 449 ms 31684 KB 
#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", DP[n]);
	for(int i = n, j = n; i > 0; --i) {
		if(i == j) {
			printf("\n%d ", i - TO[i]);
			j = TO[i];
		}
		printf("%d ", I[i]);
	}
	printf("\n");
	return 0;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Incorrect 1 ms 10588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 11612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 11684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 314 ms 28340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 449 ms 31412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 389 ms 31684 KB Output isn't correct
2 Halted 0 ms 0 KB -