oj.uz

답안 #118121

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118121 2019-06-18T08:23:51 Z scanhex Naan (JOI19_naan) C++17
29 / 100
 4000 ms 9848 KB 
#include <bits/stdc++.h>

using namespace std;
using nagai = long long;
using big=__int128;
using unagai=unsigned long long;
using ll=long long;
#define sz(x) int((x).size())

const int N=4040;
int n,m;
nagai matr[N][N];
nagai pref[N][N];
nagai gcd(nagai a,nagai b){
	while(b){
		 a%=b,swap(a,b);
	}
	return a;
}
struct frac;
frac find(frac a,frac b);
const nagai C=1000000000LL;
struct frac{
	nagai a,b;
	frac(){}
	void find(){
		if(b<=C)return;
		frac r(a+1,b,0);
		int it=0;
		while(true){
			frac nw=::find(*this,r);
//			cerr<<r.a<<' '<<r.b<<'\n';
			if(nw.b>C){
				a=r.a,b=r.b;
				return;
			}
			r=nw;
		}
	}
	void check(){
		if(a==0)return;
		nagai g=gcd(a,b);
		a/=g;
		b/=g;
		find();
	}
	frac(nagai a,nagai b,bool ch=true):a(a),b(b){
		if(ch)
			check();
	}
	frac(nagai x):a(x),b(1){}
	frac operator *(frac o){
		return frac(a*o.a,b*o.b);
	}
	frac operator +(frac o){
		return frac(a*o.b+o.a*b,b*o.b);
	}
	frac operator -(frac o){
		return frac(a*o.b-o.a*b,b*o.b);
	}
	bool operator <=(frac o){
		return a*o.b<=b*o.a;
	}
	bool operator <(frac o){
		return a*o.b<b*o.a;
	}
};
frac find(frac l, frac r){
	//cerr<<l.a<<' '<<l.b<<' '<<r.a<<' '<<r.b<<'\n';
	if(l.a>=l.b){
		nagai d=l.a/l.b;
		frac ans=find(frac(l.a-l.b*d,l.b,0),frac(r.a-r.b*d,r.b,0));
		ans.a+=ans.b*d;
		return ans;
	}
	if(r.a>r.b)
		return 1;
	frac ans=find(frac(r.b,r.a,0),frac(l.b,l.a,0));
	swap(ans.a,ans.b);
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j){
			ll x;
			cin>>x;
			matr[i][j]=x;
			pref[i][j+1]=pref[i][j]+matr[i][j];
		}
	frac cur(0);
	vector<frac>fr;
	vector<int>ord;
	vector<bool>used(n);
	for(int i=0;i<n;++i){
		frac mn(1e9);
		int mni=-1;
		for(int j=0;j<n;++j){
			if(used[j])continue;
			int lb=cur.a/cur.b;
			frac kek=frac(matr[j][lb])*frac(cur.a%cur.b,cur.b);
			int L=lb,R=m+1;
			while(R-L>1){
				int M=(L+R)/2;
				if(frac(pref[j][M])<=frac(pref[j][m],n)+pref[j][lb]+kek)
					L=M;
				else
					R=M;
			}
			frac rest(0);
			if(L==lb){
				rest=frac(pref[j][m],n)*frac(1,matr[j][L])+cur;
			}
			else{
				rest=frac(pref[j][m],n)-(frac(pref[j][L])-pref[j][lb]-kek);
				if(rest.a)
					rest=rest*frac(1,matr[j][L]);
				rest=rest+frac(L);
			}
			if(rest<mn)
				mn=rest,mni=j;
		}
		cur=mn;
//		cerr<<cur.a<<' '<<cur.b<<'\n';
		fr.push_back(cur);
		ord.push_back(mni);
		used[mni]=true;
	}
	for(int i=0;i<n-1;++i){
		cout<<(ll)fr[i].a<<' '<<(ll)fr[i].b<<'\n';
	}
	for(int i=0;i<n;++i)
		cout<<ord[i]+1<<' ';
	cout<<'\n';

	return 0;
}

Compilation message

naan.cpp: In member function 'void frac::find()':
naan.cpp:29:7: warning: unused variable 'it' [-Wunused-variable]
   int it=0;
       ^~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 3 ms 640 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 3 ms 640 KB Output is correct
19 Correct 2 ms 640 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 2 ms 640 KB Output is correct
23 Correct 2 ms 432 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 3 ms 512 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 2 ms 512 KB Output is correct

Subtask #3
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 512 KB Output is correct
29 Correct 3 ms 640 KB Output is correct
30 Correct 2 ms 512 KB Output is correct
31 Correct 3 ms 512 KB Output is correct
32 Correct 2 ms 512 KB Output is correct
33 Correct 3 ms 640 KB Output is correct
34 Correct 2 ms 640 KB Output is correct
35 Correct 3 ms 512 KB Output is correct
36 Correct 3 ms 512 KB Output is correct
37 Correct 2 ms 640 KB Output is correct
38 Correct 2 ms 432 KB Output is correct
39 Correct 3 ms 512 KB Output is correct
40 Correct 3 ms 512 KB Output is correct
41 Correct 2 ms 512 KB Output is correct
42 Correct 2 ms 512 KB Output is correct
43 Execution timed out 4097 ms 9848 KB Time limit exceeded
44 Halted 0 ms 0 KB -