Submission #244592

#	Time	Username	Problem	Language	Result	Execution time	Memory
244592		TadijaSebez	Teams (CEOI11_tea)	C++11	100 / 100	1012 ms	153324 KiB

tea

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int N=1000050;
const int inf=1e9+7;
void ckmx(int&x,int y){x=max(x,y);}
int a[N],ord[N],n,dp[N],go[N],dp_sz[N];
int myx(int x,int y,int t){
	if(x==-1)return y;
	if(y==-1)return x;
	if(dp[x]>dp[y])return x;
	if(dp[y]>dp[x])return y;
	if(t==1){
		if(dp_sz[x]<dp_sz[y])return x;
		else return y;
	}else{
		if(x>y)return x;
		else return y;
	}
	//return x==-1?y:y==-1?x:mp(dp[x],t==1?-dp_sz[x]:x)>mp(dp[y],t==1?-dp_sz[y]:y)?x:y;
}
struct ST{
	int sgt[N*2],t;
	void cl(){for(int i=1;i<n*2;i++)sgt[i]=-1;}
	void Set(int i,int f){i+=n;sgt[i]=f;for(i>>=1;i;i>>=1)sgt[i]=myx(sgt[i<<1],sgt[i<<1|1],t);}
	int Get(int l,int r){
		l=max(l,0);r=min(r,n-1);
		int ans=-1;
		for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
			if(l%2==1)ans=myx(ans,sgt[l++],t);
			if(r%2==0)ans=myx(ans,sgt[r--],t);
		}
		return ans;
	}
}ST1;
struct BT{
	int bit[N],t;
	void cl(){for(int i=1;i<=n;i++)bit[i]=-1;}
	void Set(int i,int f){for(i++;i<=n;i+=i&-i)bit[i]=myx(bit[i],f,t);}
	int Get(int l,int r){int ans=-1;for(r++;r>0;r-=r&-r)ans=myx(ans,bit[r],t);return ans;}
}ST2;
vector<int> izb[N];
int DP(){
	dp[0]=0;
	dp_sz[0]=0;
	ST1.cl();ST2.cl();
	for(int i=1;i<=n;i++){
		ST1.Set(i-1,i-1);
		for(int j:izb[i]){
			ST1.Set(j,-1);
			ST2.Set(j,j);
		}
		dp[i]=-inf;
		//go[i]=Get(i-lim,i-a[i]);
		//if(go[i]!=-1)dp[i]=dp[go[i]]+1;
		/*for(int j=0;j<=i-a[i];j++){
			if(dp[i]<dp[j]+1){
				dp[i]=dp[j]+1;
				dp_sz[i]=max(dp_sz[j],i-j);
				go[i]=j;
			}else if(dp[i]==dp[j]+1){
				if(dp_sz[i]>max(dp_sz[j],i-j))
					dp_sz[i]=max(dp_sz[j],i-j),
					go[i]=j;
			}
		}*/
		auto cons=[&](int j){
			if(dp[i]<dp[j]+1){
				dp[i]=dp[j]+1;
				dp_sz[i]=max(dp_sz[j],i-j);
				go[i]=j;
			}else if(dp[i]==dp[j]+1){
				if(dp_sz[i]>max(dp_sz[j],i-j))
					dp_sz[i]=max(dp_sz[j],i-j),
					go[i]=j;
			}
		};
		int j=ST1.Get(0,i-a[i]);
		if(j!=-1)cons(j);
		int k=ST2.Get(0,i-a[i]);
		if(k!=-1)cons(k);
		if(dp[i]>=0){
			if(i+dp_sz[i]<=n)
				izb[i+dp_sz[i]].pb(i);
		}
	}
	return dp[n];
}
int main(){
	ST1.t=1;
	ST2.t=2;
	scanf("%i",&n);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]),ord[i]=i;
	sort(ord+1,ord+1+n,[&](int i,int j){return a[i]<a[j];});
	sort(a+1,a+1+n);
	DP();
	vector<vector<int>> sol;
	for(int i=n;i>0;i=go[i]){
		vector<int> tmp;
		for(int j=i;j>go[i];j--)
			tmp.push_back(ord[j]);
		sol.push_back(tmp);
	}
	printf("%i\n",sol.size());
	for(auto v:sol){
		printf("%i ",v.size());
		for(int i:v)printf("%i ",i);
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

tea.cpp: In function 'int main()':
tea.cpp:105:26: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<std::vector<int> >::size_type {aka long unsigned int}' [-Wformat=]
  printf("%i\n",sol.size());
                ~~~~~~~~~~^
tea.cpp:107:24: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%i ",v.size());
                ~~~~~~~~^
tea.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
tea.cpp:94:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%i",&a[i]),ord[i]=i;
                       ~~~~~~~~~~~~~~~~~^~~~~~~~~

• 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