oj.uz

Submission #245027

# Submission time Handle Problem Language Result Execution time Memory
245027 2020-07-05T11:09:07 Z kshitij_sodani Naan (JOI19_naan) C++17
5 / 100
 7 ms 768 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> pos){
	/*if(pos.b==0){
		while(true){
			continue;
		}
	}*/
	pair<llo,llo> val={aa[ind][pos.a/pos.b]*(pos.b-(pos.a%pos.b)),pos.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);
				//cout<<j<<":"<<x.a<<":"<<x.b<<endl;
				/*if(pos.a/pos.b>=l){
					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;
						}
					}
*/	

					tt.b*=aa[j][pos.a/pos.b];
				/*	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);
		}

		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 4 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 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 432 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 6 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

Subtask #2
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 Runtime error 7 ms 768 KB Execution killed with signal 8 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 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 432 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 6 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 384 KB Output is correct
18 Runtime error 7 ms 768 KB Execution killed with signal 8 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -