Submission #533319

#	Time	Username	Problem	Language	Result	Execution time	Memory
533319		codr0	Naan (JOI19_naan)	C++14	29 / 100	4096 ms	42932 KiB

naan

// Code by Parsa Eslami
 
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define bit(i,j) ((j>>i)&1)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
 
using namespace std;

	pii simp(pii X){
		int gc=__gcd(X.F,X.S);
		X.S/=gc;
		X.F/=gc;
		return X;
	}

	pii sum(pii a,pii b){// a+b
		a=simp(a);
		b=simp(b);
		pii rt;
		int gc=__gcd(a.S,b.S);
		rt.S=a.S*b.S/gc;
		rt.F=a.F*(b.S/gc)+b.F*(a.S/gc);
		rt=simp(rt);
		return rt;
	}

	pii mul(pii a,pii b){// a*b
		a=simp(a);
		b=simp(b);
		pii rt;
		rt.F=a.F*b.F;
		rt.S=a.S*b.S;
		rt=simp(rt);
		return rt;
	}

	pii L(pii a,pii b){// a-b
		b.F=-b.F;
		return sum(a,b);
	}

	pii div(pii a,pii b){// a/b
		swap(b.F,b.S);
		return mul(a,b);
	}

	bool cmp(pii a,pii b){// a<=b
		a=simp(a);
		b=simp(b);
		return (a.F*b.S<=a.S*b.F);
	}

	int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n,l; cin>>n>>l;
	int v[n+1][l+1];
	FOR(i,1,n) FOR(j,1,l) cin>>v[i][j];
	pii a[n][n];
	FOR(i,1,n){
		pii point={0,1};//
		pii S={0,1};//
		int ind=1;//
		int Sp=0;
		FOR(j,1,l) Sp+=v[i][j];
		pii targ={Sp,n};
		FOR(j,1,n-1){
			while(1){
				pii l=div(L(targ,S),{v[i][ind],1});
				if(cmp(sum(l,point),{1,1})){
					a[i][j]=sum({ind-1,1},sum(l,point));
					point=sum(l,point);
					S={0,1};
					if(point.F==point.S){
						ind++;
						point={0,1};
					}
					break;
				}else{
					S=sum(S,mul(L({1,1},point),{v[i][ind],1}));
					ind++; point={0,1};
				}
			}
		}
	}
	bool mark[n+1]={};
	int p[n+1]={};
	FOR(i,1,n-1){
		pair<pii,int> ans={{1e9,1},-1};
		FOR(j,1,n) if(!mark[j]){
			pair<pii,int> x0={a[j][i],j};
			if(ans.S==-1||cmp(x0.F,ans.F)) ans=x0;
		}
		mark[ans.S]=1;
		p[i]=ans.S;
		cout<<ans.F.F<<" "<<ans.F.S<<'\n';
	}
	FOR(i,1,n) if(!mark[i]) p[n]=i;
	FOR(i,1,n) cout<<p[i]<<" "; cout<<'\n';


	return 0;
	}

Compilation message (stderr)

naan.cpp: In function 'int32_t main()':
naan.cpp:7:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    7 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
      |                    ^~~
naan.cpp:108:2: note: in expansion of macro 'FOR'
  108 |  FOR(i,1,n) cout<<p[i]<<" "; cout<<'\n';
      |  ^~~
naan.cpp:108:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  108 |  FOR(i,1,n) cout<<p[i]<<" "; cout<<'\n';
      |                              ^~~~

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