제출 #1296104

#제출 시각아이디문제언어결과실행 시간메모리
1296104PieArmyBrought Down the Grading Server? (CEOI23_balance)C++20
0 / 100
2096 ms27724 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)

struct Seg{
	int n;
	vector<int>tree;
	void init(int N){
		n=N;
		tree.clear();
		tree.resize(n<<1,0);
	}
	int l,r;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]++;
			return;
		}
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		tree[node]=min(tree[node*2],tree[node*2+1]);
	}
	void update(int tar){
		l=tar;
		up();
	}
};

int n,s,t;
int cnt[100023],per[100023];
map<int,int>mp[100023];
vector<int>ans[100023];
vector<int>ek;
Seg seg[100023];

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>s>>t;
	for(int i=0;i<n;i++){
		seg[i].init(s);
		ans[i].resize(s,0);
		for(int j=0;j<s;j++){
			int x;cin>>x;
			x--;
			mp[x][i]++;
			cnt[x]++;
		}
	}
	for(int i=0;i<t;i++){
		per[i]=i;
	}
	sort(per,per+t,[&](const int &x,const int &y){
		return cnt[x]<cnt[y];
	});
	int bas=0;
	Seg seg2;
	for(int i=0;i<t;i++){
		seg2.init(s);
		for(int j=1;cnt[per[i]]>=s;j++,bas++){
			for(int pos=bas-1;seg2.tree[1]<j;){
				auto itr=mp[per[i]].upper_bound(pos);
				if(itr==mp[per[i]].end()){
					itr=mp[per[i]].begin();
				}
				pos=itr->fr;
				while(itr->sc&&seg2.tree[1]<j){
					int node=1,left=0,right=s-1;
					while(left!=right){
						if(seg2.tree[node*2+1]==j||seg[pos].tree[node*2+1]){
							node*=2;
							right=mid;
						}
						else{
							node*=2;node++;
							left=mid+1;
						}
					}
					if(seg[pos].tree[node]||seg2.tree[node]==j)break;
					itr->sc--;
					cnt[per[i]]--;
					seg2.update(left);
					ans[pos][left]=per[i]+1;
					seg[pos].update(left);
				}
				if(!itr->sc)mp[per[i]].erase(itr);
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<s;j++){
			cout<<ans[i][j]<<" ";
		}
		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...