oj.uz

Submission #1111436

# Submission time Handle Problem Language Result Execution time Memory
1111436 2024-11-12T08:27:56 Z ahihi Teams (CEOI11_tea) C++14
100 / 100
 181 ms 28704 KB 
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int n,Ans,Min,Max[maxn],f[maxn],lst[maxn],L,R,mid;
struct lc{
	int x,id;
	bool operator <(const lc b)const{return x<b.x;}
}a[maxn];
inline int read(){
	int ret=0;char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
	return ret;
}
inline int check(int len){
	memset(lst,0,sizeof lst);
	memset(f,-1,sizeof f);
	memset(Max,-1,sizeof Max);
	Max[0]=0;int inf=Max[1];
	for (int i=1;i<=n;i++){
		if (a[i].x<=i&&Max[i-a[i].x]>=0&&lst[i-a[i].x]+len>=i) f[i]=Max[i-a[i].x]+1;     //判断是否能新成一个组 
		if (f[i]>=Max[i-1]) lst[i]=i,Max[i]=f[i];
		else lst[i]=lst[i-1],Max[i]=Max[i-1];
	}
	return f[n];           //返回最大组数 
}
int main(){
	n=read();
	for (int i=1;i<=n;i++) a[i]=(lc){read(),i};
	sort(a+1,a+n+1); 
	printf("%d\n",Min=check(n));     //记录最大组数 
	L=0,Ans=R=n;
	while (L<=R){
		mid=L+R>>1;
		if (check(mid)==Min) Ans=mid,R=mid-1;       //查找满足最大组数的前提下mid最小为多少 
		else L=mid+1;
	}
	check(Ans),R=n;       //最后要在check一遍来计算lst数组 
	while (R){  
		L=lst[R-a[R].x];
		printf("%d",R-L);
		for (int i=L+1;i<=R;i++) printf(" %d",a[i].id); //输出答案 
	    putchar('\n');R=L;
	}
	return 0;
}

Compilation message

tea.cpp: In function 'int check(int)':
tea.cpp:19:15: warning: unused variable 'inf' [-Wunused-variable]
   19 |  Max[0]=0;int inf=Max[1];
      |               ^~~
tea.cpp: In function 'int main()':
tea.cpp:34:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   mid=L+R>>1;
      |       ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13648 KB Output is correct
2 Correct 4 ms 13648 KB Output is correct
3 Correct 4 ms 13648 KB Output is correct
4 Correct 4 ms 13648 KB Output is correct
5 Correct 4 ms 13648 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13816 KB Output is correct
2 Correct 5 ms 13648 KB Output is correct
3 Correct 5 ms 13648 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13816 KB Output is correct
2 Correct 5 ms 13648 KB Output is correct
3 Correct 5 ms 13648 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13648 KB Output is correct
2 Correct 7 ms 13648 KB Output is correct
3 Correct 7 ms 13816 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13648 KB Output is correct
2 Correct 6 ms 13648 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 16208 KB Output is correct
2 Correct 17 ms 16208 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16208 KB Output is correct
2 Correct 15 ms 16356 KB Output is correct
3 Correct 19 ms 16208 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 25160 KB Output is correct
2 Correct 97 ms 25212 KB Output is correct
3 Correct 119 ms 25160 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 26696 KB Output is correct
2 Correct 164 ms 28704 KB Output is correct
3 Correct 135 ms 26952 KB Output is correct
4 Correct 150 ms 25968 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 26736 KB Output is correct
2 Correct 125 ms 26912 KB Output is correct
3 Correct 149 ms 26704 KB Output is correct
4 Correct 181 ms 26696 KB Output is correct