Submission #1296381

#TimeUsernameProblemLanguageResultExecution timeMemory
1296381PieArmyBrought Down the Grading Server? (CEOI23_balance)C++20
100 / 100
448 ms83372 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

int n,s,t,m,k;
int cnt[200023],id[200023],sira[200023];
vector<int>arr[200023],brr[200023],ans[200023];
vector<pair<int,int>>locs[200023];
vector<int>occ[200023];
int nexcol=0;

int deg[400023];
vector<pair<int,int>>komsu[400023];

void f(vector<pair<int,int>>v){
	if(v.size()==m){
		for(auto&x:v){
			ans[x.fr][nexcol]=id[x.sc];
		}
		nexcol++;
		return;
	}
	vector<pair<int,int>>vv[2];
	for(int i=0;i<v.size();i++){
		pair<int,int>x=v[i];
		komsu[x.fr].pb({m+x.sc,i});
		komsu[m+x.sc].pb({x.fr,i});
		deg[x.fr]++;
		deg[m+x.sc]++;
	}
	for(int i=1;i<=k+m;i++){
		int pos=i;
		int bit=0;
		while(deg[pos]){
			while(v[komsu[pos].back().sc].fr<0)komsu[pos].pop_back();
			pair<int,int>x=komsu[pos].back();
			deg[x.fr]--;
			deg[pos]--;
			vv[bit].pb(v[x.sc]);
			bit^=1;
			v[x.sc].fr*=-1;
			pos=x.fr;
		}
	}
	for(int i=1;i<=k+m;i++){
		komsu[i].clear();
	}
	f(vv[0]);
	f(vv[1]);
}

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>s>>t;
	for(int i=1;i<=n;i++){
		arr[i].resize(s,0);
		brr[i].resize(s,0);
		for(int j=0;j<s;j++){
			cin>>arr[i][j];
			brr[i][j]=arr[i][j];
			cnt[arr[i][j]]++;
			locs[arr[i][j]].pb({i,j});
		}
	}
	for(int i=1;i<=t;i++){
		while(cnt[i]>s){
			cnt[++t]+=s;
			cnt[i]-=s;
			for(int j=0;j<s;j++){
				locs[t].pb(locs[i].back());
				brr[locs[i].back().fr][locs[i].back().sc]=t;
				locs[i].pop_back();
			}
		}
	}
	{
		set<pair<int,int>>st;
		for(int i=1;i<=t;i++){
			auto itr=st.begin();
			if(itr!=st.end()&&itr->fr+cnt[i]<=s){
				int tar=itr->sc;
				cnt[tar]+=cnt[i];
				cnt[i]=0;
				while(locs[i].size()){
					locs[tar].pb(locs[i].back());
					brr[locs[i].back().fr][locs[i].back().sc]=tar;
					locs[i].pop_back();
				}
				st.erase(itr);
				st.insert({cnt[tar],tar});
			}
			else st.insert({cnt[i],i});
		}
	}
	m=n;
	for(int i=1;i<=t;i++){
		while(cnt[i]%s){
			if(brr[m].size()==s)m++;
			locs[i].pb({m,brr[m].size()});
			brr[m].pb(i);
			cnt[i]++;
		}
		if(cnt[i]){
			id[++k]=i;
			sira[i]=k;
		}
	}
	vector<pair<int,int>>v;
	for(int i=1;i<=m;i++){
		ans[i].resize(s,0);
		for(int j=0;j<s;j++){
			v.pb({i,sira[brr[i][j]]});
		}
	}
	f(v);
	for(int i=1;i<=n;i++){
		for(int j=0;j<s;j++){
			occ[brr[i][j]].pb(j);
		}
		for(int j=0;j<s;j++){
			int x=ans[i][j];
			ans[i][j]=arr[i][occ[ans[i][j]].back()];
			cout<<ans[i][j]<<" ";
			occ[x].pop_back();
		}
		cout<<endl;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...