Submission #131830

#	Time	Username	Problem	Language	Result	Execution time	Memory
131830		hamzqq9	Naan (JOI19_naan)	C++14	29 / 100	501 ms	8236 KiB

naan

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define N 2019
#define MOD 998244353
using namespace std;

#define greater bos

struct frac {

	int u,d;

};

frac mul(frac a,frac b) {

	ll u=(ll)a.u*b.u;
	ll d=(ll)a.d*b.d;

	ll g=__gcd(abs(u),abs(d));

	return {u/g,d/g};

}

frac dvd(frac a,frac b) {

	swap(b.u,b.d);

	return mul(a,b);

}

frac sub(frac a,frac b) {

	ll u=(ll)a.u*b.d-(ll)b.u*a.d;
	ll d=(ll)a.d*b.d;

	ll g=__gcd(abs(u),abs(d));

	return {u/g,d/g};

}

frac add(frac a,frac b) {

	ll u=(ll)a.u*b.d+(ll)b.u*a.d;
	ll d=(ll)a.d*b.d;

	ll g=__gcd(abs(u),abs(d));

	return {u/g,d/g};

}

bool eq(frac a,frac b) {

	return (ll)a.u*b.d==(ll)b.u*a.d;

}

bool greateq(frac a,frac b) {
	
	return (ll)a.u*b.d>=(ll)b.u*a.d;	

}

bool greater(frac a,frac b) {
	
	return (ll)a.u*b.d>(ll)b.u*a.d;	

}

frac gmin(frac a,frac b) {

	return greater(a,b)?b:a;	

}

int gnext(frac a) {

	return a.u/a.d+1;

}

int n,l;
int v[N][N],u[N],ptr[N];
frac req[N];
vector<frac> cp[N];

int main() {

	scanf("%d %d",&n,&l);

	for(int i=1;i<=n;i++) {

		req[i]={0,n};

		for(int j=1;j<=l;j++) {

			scanf("%d",&v[i][j]);

			req[i].u+=v[i][j];

		}

	}	

	for(int i=1;i<=n;i++) {

		//cerr<<i<<"\n";

		frac cur={0,1};

		while(sz(cp[i])<n) {

			//cerr<<cur.u<<" "<<cur.d<<"\n";

			cp[i].pb(cur);

			frac rq=req[i];

			for(int j=gnext(cur);j<=l;j++) {

				//cerr<<j<<" "<<cur.u<<" "<<cur.d<<"\n";

				frac df=sub({j,1},cur);
				frac sum=mul(df,{v[i][j],1});

				if(greateq(sum,rq)) {

					frac go=dvd(rq,{v[i][j],1});

					cur=add(cur,go);

					break ;

				}
				else {

					rq=sub(rq,sum);
					cur={j,1};

				}

			}

		}

		cp[i].pb({l,1});

	}

	for(int i=1;i<=n;i++) {

		//cerr<<"--------------------------\n";

		//for(auto x:cp[i]) printf("%d %d\n",x.u,x.d);

	}

		//cerr<<"--------------------------\n";

	//cerr<<"OK\n";

	vector<frac> res;
	vector<int> ans;

	for(int i=1;i<=n;i++) {

		frac mn={inf,1};
		int tut=-1;

		for(int j=1;j<=n;j++) {

			if(u[j]) continue ;

			while(sz(res) && ptr[j]<n && greater(res.back(),cp[j][ptr[j]])) {

				++ptr[j];

			}

			if(ptr[j]<n) {
			
				mn=gmin(mn,cp[j][ptr[j]+1]);

				if(eq(mn,cp[j][ptr[j]+1])) {

					tut=j;

				}

			}

		}

		ans.pb(tut);
		u[tut]=1;

		res.pb(mn);

	}

	res.ppb();

	for(auto x:res) printf("%d %d\n",x.u,x.d);

	for(auto x:ans) printf("%d ",x);

}

Compilation message (stderr)

naan.cpp: In function 'frac mul(frac, frac)':
naan.cpp:31:11: warning: narrowing conversion of '(u / g)' from 'long long int' to 'int' inside { } [-Wnarrowing]
  return {u/g,d/g};
          ~^~
naan.cpp:31:15: warning: narrowing conversion of '(d / g)' from 'long long int' to 'int' inside { } [-Wnarrowing]
  return {u/g,d/g};
              ~^~
naan.cpp: In function 'frac sub(frac, frac)':
naan.cpp:50:11: warning: narrowing conversion of '(u / g)' from 'long long int' to 'int' inside { } [-Wnarrowing]
  return {u/g,d/g};
          ~^~
naan.cpp:50:15: warning: narrowing conversion of '(d / g)' from 'long long int' to 'int' inside { } [-Wnarrowing]
  return {u/g,d/g};
              ~^~
naan.cpp: In function 'frac add(frac, frac)':
naan.cpp:61:11: warning: narrowing conversion of '(u / g)' from 'long long int' to 'int' inside { } [-Wnarrowing]
  return {u/g,d/g};
          ~^~
naan.cpp:61:15: warning: narrowing conversion of '(d / g)' from 'long long int' to 'int' inside { } [-Wnarrowing]
  return {u/g,d/g};
              ~^~
naan.cpp: In function 'int main()':
naan.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&l);
  ~~~~~^~~~~~~~~~~~~~~
naan.cpp:110:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&v[i][j]);
    ~~~~~^~~~~~~~~~~~~~~

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