oj.uz

Submission #245059

# Submission time Handle Problem Language Result Execution time Memory
245059 2020-07-05T11:34:59 Z kshitij_sodani Naan (JOI19_naan) C++17
29 / 100
 114 ms 4732 KB 
/*
 
*/
#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);
	aa.a/=cc;
	aa.b/=cc;
	
	return aa;
}

pair<llo,llo> simp2(pair<llo,llo> aa){
	llo cc=gcd(aa.a,aa.b);
	aa.a/=cc;
	aa.b/=cc;
	
	/*if(aa.b>1e9){
		return simp2()
		return simp2({(aa.a+1)/2,(aa.b+1)/2});
	}*/
	return aa;
}
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/(llo)2)+1,pos.b/(llo)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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 416 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 512 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 6 ms 512 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 6 ms 512 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 512 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 6 ms 384 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 416 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 512 KB Output is correct
33 Correct 6 ms 384 KB Output is correct
34 Correct 6 ms 384 KB Output is correct
35 Correct 6 ms 512 KB Output is correct
36 Correct 6 ms 384 KB Output is correct
37 Correct 6 ms 512 KB Output is correct
38 Correct 5 ms 384 KB Output is correct
39 Correct 5 ms 512 KB Output is correct
40 Correct 5 ms 384 KB Output is correct
41 Correct 5 ms 384 KB Output is correct
42 Correct 6 ms 384 KB Output is correct
43 Incorrect 114 ms 4732 KB Integer parameter [name=A_i] equals to 2109834534371, violates the range [1, 2000000000000]
44 Halted 0 ms 0 KB -