oj.uz

답안 #57816

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57816 2018-07-16T09:19:58 Z ainta(#1666) Teams (CEOI11_tea) C++11
30 / 100
 522 ms 40452 KB 
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
struct point {
	int x, num;
	bool operator <(const point &p)const {
		return x > p.x;
	}
}w[1010000];
int Deq[1010000], head, tail, P[1010000], U[1010000], BB[1010000], EE[1010000];
int Get(int M) {
	int i, r = 0, res = 0;
	head = 1, tail = 0;
	int b = 1, e = 1;
	Deq[++tail] = 1;
	while (1) {
		BB[r] = b, EE[r] = e, U[r] = Deq[head];
		int b2, e2;
		e2 = min(n + 1, e + M);
		if (head > tail)break;
		b2 = P[Deq[head]];
		if (b2 > e2)break;
		r++;
		if (e2 == n + 1) {
			res = r;
		}
		while (e < e2) {
			e++;
			if (e == n + 1)continue;
			while (head <= tail && P[Deq[tail]] >= P[e])tail--;
			Deq[++tail] = e;
		}
		while (head <= tail && Deq[head] < b2)head++;
		b = b2;
	}
	return res;
}
void Print(int b, int e) {
	printf("%d ", e - b);
	for (int i = b; i < e; i++)printf("%d ", w[i].num);
	puts("");
}
int main() {
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i].x);
		w[i].num = i;
	}
	sort(w + 1, w + n + 1);
	for (i = 1; i <= n; i++)P[i] = i + w[i].x;
	int pv = 0, cnt = 0;
	while (1) {
		cnt++;
		pv += w[pv + 1].x;
		if (pv > n)cnt--;
		if (pv >= n)break;
	}
	int b = w[1].x, e = n, mid, res;
	while (b <= e) {
		mid = (b + e) >> 1;
		if (Get(mid) == cnt) {
			res = mid;
			e = mid - 1;
		}
		else b = mid + 1;
	}
	Get(res);
	printf("%d\n", cnt);
	pv = n + 1;
	int cur = cnt;
	while (cur) {
		if (pv - res >= BB[cur - 1]) {
			Print(pv - res, pv);
			pv -= res;
		}
		else {
			Print(U[cur - 1], pv);
			pv = U[cur - 1];
		}
		cur--;
	}
	return 0;
}

Compilation message

tea.cpp: In function 'int Get(int)':
tea.cpp:13:6: warning: unused variable 'i' [-Wunused-variable]
  int i, r = 0, res = 0;
      ^
tea.cpp: In function 'int main()':
tea.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
tea.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i].x);
   ~~~~~^~~~~~~~~~~~~~~
tea.cpp:69:5: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  Get(res);
  ~~~^~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 2 ms 432 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 480 KB Output is correct
2 Incorrect 2 ms 508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 5 ms 764 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 2388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 2608 KB Output is correct
2 Correct 25 ms 2608 KB Output is correct
3 Correct 37 ms 3232 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 297 ms 18136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 504 ms 23756 KB Output is correct
2 Correct 522 ms 40452 KB Output is correct
3 Incorrect 323 ms 40452 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 40452 KB Output is correct
2 Correct 283 ms 40452 KB Output is correct
3 Incorrect 418 ms 40452 KB Output isn't correct
4 Halted 0 ms 0 KB -