Submission #1111436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111436		ahihi	Teams (CEOI11_tea)	C++14	100 / 100	181 ms	28704 KiB

tea

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10