Submission #40429511

---

Source Code Expand

//ANMHLIJKTJIY!
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 52
using namespace std;
struct Edge{
	ll v,bkid,cap;
};
struct Flow{
	vector<Edge> vt[N<<1];
	ll n,m,s,t,dep[N<<1],cur[N<<1],lstfl[N][N];
	void init(ll _n)
	{
		n=_n,m=0,s=_n-2,t=_n-1;
		ll i;
		memset(lstfl,0,sizeof(lstfl));
		for(i=0;i<n;i++)
		{
			vt[i].clear();
		}
		return;
	}
	void addedge(ll x,ll y,ll w)
	{
		Edge cr;
		cr.v=y,cr.bkid=vt[y].size(),cr.cap=w;
		vt[x].push_back(cr);
		cr.v=x,cr.bkid=vt[x].size()-1,cr.cap=0;
		vt[y].push_back(cr);
		return;
	}
	bool bfs()
	{
		ll i,x;
		for(i=0;i<n;i++)
		{
			dep[i]=LINF;
		}
		queue<ll> q;
		q.push(s);
		dep[s]=0;
		while(!q.empty())
		{
			x=q.front();
			q.pop();
			for(i=0;i<vt[x].size();i++)
			{
				if(vt[x][i].cap!=0)
				{
					if(dep[vt[x][i].v]>dep[x]+1)
					{
						dep[vt[x][i].v]=dep[x]+1;
						q.push(vt[x][i].v);
					}
				}
			}
		}
		return (dep[t]<INF);
	}
	ll dfs(ll x,ll lft)
	{
		if(x==t||lft<=0)
		{
			return lft;
		}
		ll i,v,ret=0;
		for(i=cur[x];i<vt[x].size();i++,cur[x]++)
		{
			if(vt[x][i].cap>0&&dep[vt[x][i].v]==dep[x]+1)
			{
				v=dfs(vt[x][i].v,min(lft,vt[x][i].cap));
				ret+=v;
				vt[x][i].cap-=v;
				vt[vt[x][i].v][vt[x][i].bkid].cap+=v;
				lft-=v;
				if(lft<=0)
				{
					break;
				}
			}
		}
		return ret;
	}
	ll maxflow()
	{
		ll ret=0,i;
		while(bfs())
		{
			for(i=0;i<n;i++)
			{
				cur[i]=0;
			}
			ret+=dfs(s,LINF);
		}
		return ret;
	}
	vector<ll> print(ll _n)
	{
		ll i,j;
		vector<ll> ret;
		for(i=0;i<_n;i++)
		{
			for(j=0;j<vt[i].size();j++)
			{
				if(vt[i][j].v==s)
				{
					continue;
				}
				if(vt[vt[i][j].v][vt[i][j].bkid].cap)
				{
					ret.push_back(vt[i][j].v-_n);
				}
			}
		}
		return ret;
	}
}fl;
ll n,a[N],s[N][N],val[N][N],b[N],sum=0,ord[N];
bool cmp(ll x,ll y)
{
	return b[x]<b[y];
}
bool check(ll v)
{
	ll tot=sum+v*n*(n+1)/2,i,j;
	if(tot%n!=0)
	{
		return false;
	}
	tot/=n;
	for(i=0;i<n;i++)
	{
		if(a[i]>tot)
		{
			return false;
		}
		b[i]=tot-a[i];
	}
	for(i=0;i<n;i++)
	{
		s[i][0]=v;
	}
	ll lstid=0;
	for(i=1;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			s[j][i]=s[j][i-1]-v/n;
		}
		ll lft=v%n;
		while(lft--)
		{
			s[lstid][i]--;
			lstid=(lstid+1)%n;
		}
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			b[i]-=s[i][j];
		}
		b[i]=-b[i];
		ord[i]=i;
	}
	while(true)
	{
		sort(ord,ord+n,cmp);
		if(b[ord[0]]==0&&b[ord[n-1]]==0)
		{
			return true;
		}
		ll x=ord[0],tks=0;
		for(i=1;i<n&&b[x]<0;i++)
		{
			for(j=n-1;s[x][i]<s[x][i-1]&&j>=0;j--)
			{
				ll curval=min(s[x][i-1]-s[x][i],s[ord[j]][i]-(i==n-1?0:s[ord[j]][i+1]));
				curval=min(curval,min(b[ord[j]],-b[x]));
				if(curval>0)
				{
					tks+=curval;
					b[x]+=curval;
					b[ord[j]]-=curval;
					s[x][i]+=curval;
					s[ord[j]][i]-=curval;
				}
			}
		}
		if(!tks)
		{
			return false;
		}
	}
	return true;
}
void print(ll v)
{
//	cout<<"ok: "<<v<<endl;
	ll i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			val[i][j]=s[i][j]-(j==n-1?0:s[i][j+1]);
		}
	}
	puts("Yes");
	printf("%lld\n",v);
	while(v--)
	{
		fl.init(n+n+2);
		for(i=0;i<n;i++)
		{
			fl.addedge(fl.s,i,1);
			fl.addedge(i+n,fl.t,1);
			for(j=0;j<n;j++)
			{
				fl.addedge(i,j+n,val[i][j]);
			}
		}
		fl.maxflow();
		vector<ll> ret=fl.print(n);
		for(i=0;i<ret.size();i++)
		{
			printf("%lld ",ret[i]+1);
			val[i][ret[i]]--;
		}
		puts("");
	}
	return;
}
int main(){
	ll i;
	scanf("%lld",&n);
	for(i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	for(i=0;i<=10000;i++)
	{
		if(check(i))
		{
			print(i);
			return 0;
		}
	}
	puts("No");
	return 0;
}

Submission Info

Compile Error

./Main.cpp:5:30: warning: ‘-fwhole-program’ is not an option that controls warnings [-Wpragmas]
    5 | #pragma GCC diagnostic error "-fwhole-program"
      |                              ^~~~~~~~~~~~~~~~~
./Main.cpp:6:30: warning: ‘-fcse-skip-blocks’ is not an option that controls warnings [-Wpragmas]
    6 | #pragma GCC diagnostic error "-fcse-skip-blocks"
      |                              ^~~~~~~~~~~~~~~~~~~
./Main.cpp:7:30: warning: ‘-funsafe-loop-optimizations’ is not an option that controls warnings [-Wpragmas]
    7 | #pragma GCC diagnostic error "-funsafe-loop-optimizations"
      |                              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp: In member function ‘bool Flow::bfs()’:
./Main.cpp:58:13: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   58 |    for(i=0;i<vt[x].size();i++)
      |            ~^~~~~~~~~~~~~
./Main.cpp: In member function ‘long long int Flow::dfs(long long int, long long int)’:
./Main.cpp:79:17: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   79 |   for(i=cur[x];i<vt[x].size();i++,cur[x]++)
      |                ~^~~~~~~~~~~~~
./Main.cpp: In member function ‘std::vector<long long int> Flow::print(long long int)’:
./Main.cpp:115:13: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  115 |    for(j=0;j<vt[i].size();j++)
      |            ~^~~~~~~~~~~~~
./Main.cpp: In function ‘void print(long long int)’:
./Main.cpp:236:12: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  236 |   for(i=0;i<ret.size();i++)
      |           ~^~~~~~~~~~...

Judge Result