제출 #245049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
245049		kshitij_sodani	Naan (JOI19_naan)	C++17	29 / 100	104 ms	4736 KiB

naan

/*
 
*/
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
llo n,l;
llo aa[2001][2001];
pair<llo,llo> cost[2001];
llo su[2001];
pair<llo,llo> add(pair<llo,llo> cur,llo ind,pair<llo,llo> pos2){
	/*if(pos.b==0){
		while(true){
			continue;
		}
	}*/
	pair<llo,llo> val={aa[ind][pos2.a/pos2.b]*(pos2.b-(pos2.a%pos2.b)),pos2.b};
	
	return {cur.a*val.b+cur.b*val.a,val.b*cur.b};
}
llo gcd(llo aa,llo bb){
	if(aa==0){
		return bb;
	}
	return gcd(bb%aa,aa);
}
pair<llo,llo> simp(pair<llo,llo> aa){
	llo cc=gcd(aa.a,aa.b);
	return {aa.a/cc,aa.b/cc};
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>l;
	for(llo i=0;i<n;i++){
		for(llo j=0;j<l;j++){
			cin>>aa[i][j];
			su[i]+=aa[i][j];
		}
	}
	set<llo> cur;
	for(llo i=0;i<n;i++){
		cur.insert(i);
	}
	vector<llo> ans;
	vector<pair<llo,llo>> ans2;
	pair<llo,llo> pos={0,1};
	for(llo i=0;i<n-1;i++){
		for(llo j=0;j<n;j++){
			cost[j]={0,1};
		}
		llo ans5=-1;
		while(true){
			llo st=0;
			pair<llo,llo> mi={-1,-1};
		//cout<<pos.a<<","<<pos.b<<endl;
			for(auto j:cur){
				pair<llo,llo> x=add(cost[j],j,pos);
				x=simp(x);
				//cout<<j<<":"<<x.a<<":"<<x.b<<endl;
				/*if(pos.a/pos.b>=l){
					while(true){
						continue;
					}
				}*/
				/*if(aa[j][pos.a/pos.b]==0){
					while(true){
						continue;
					}
				}*/
				if(x.a*n>=x.b*su[j]){
					pair<llo,llo> tt={su[j]*cost[j].b-cost[j].a*n,n*cost[j].b};
					tt=simp(tt);
 
			/*		if(pos.b==0){
						while(true){
							continue;
						}
					}
*/	
 
				/*	if(pos.a/pos.b>=l){
						while(true){
							continue;
						}
					}*/
					/*if(aa[j][pos.a/pos.b]==0){
						while(true){
							continue;
						}
					}*/
					tt.b*=aa[j][pos.a/pos.b];
					tt=simp(tt);
					/*if(pos.a>=pos.b*l){
						while(true){
							continue;
						}
					}*/
			/*		if(aa[j][pos.a/pos.b]==0){
						while(true){
							continue;
						}
					}
*/
				//	cout<<tt.a<<":"<<tt.b<<endl;
					/*if(tt.b==0){
						while(true){
							continue;
						}
					}*/
					tt={tt.a*pos.b+tt.b*pos.a,pos.b*tt.b};
					tt=simp(tt);
					if(mi.a==-1){
						mi=tt;
						st=j+1;
					}
					else{
						if(tt.a*mi.b<tt.b*mi.a){
							st=j+1;
							mi=tt;
						}
					}
					continue;
				}
				cost[j]=x;
			}
 
			if(st>0){
			/*	if(mi.b==0){
					while(true){
						continue;
					}
				}*/
				pos=simp(mi);
 
				ans5=st;
				break;
			}
			pos.a+=pos.b-(pos.a%pos.b);
			/*if(pos.a>=pos.b*l){
				while(true){
					continue;
				}
			}*/
		}
		while(pos.b>(llo)(2000000000000)){
			pos={pos.a/2,pos.b/2};
		}
		/*if(pos.b>2000000000000){
			pos.b=2000000000000;
		}*/
		ans.pb(ans5);
		cur.erase(ans5-1);
		if(i<n-1){
			ans2.pb(pos);
		}
	}
	ans.pb((*(cur.begin()))+1);
	for(auto j:ans2){
		cout<<j.a<<" "<<j.b<<endl;
	}
	for(auto j:ans){
		cout<<j<<" ";
	}
	cout<<endl;
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 0 / 71