제출 #131648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131648		hamzqq9	Naan (JOI19_naan)	C++14	29 / 100	69 ms	13804 KiB

naan

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<ll,ll>
#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
using namespace std;
#define greater bos

int n,l;
ii req[N],reqq[N];
int pre[N][N],v[N][N];

ii mul(ii a,ii b) {

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

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

	return {u/g,d/g};

}

ii dvd(ii a,ii b) {

	swap(b.st,b.nd);

	return mul(a,b);

}

ii sub(ii a,ii b) {

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

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

	return {u/g,d/g};

}

ii add(ii a,ii b) {

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

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

	return {u/g,d/g};

}

bool greateq(ii a,ii b) {

	return (ll)a.st*b.nd>=(ll)b.st*a.nd;

}

bool greater(ii a,ii b) {

	return (ll)a.st*b.nd>(ll)b.st*a.nd;

}

bool eq(ii a,ii b) {

	return (ll)a.st*b.nd==(ll)b.st*a.nd;

}

ii gmin(ii a,ii b) {

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

ll get_nxt(ii a) {

	ll d=(a.st+a.nd)/a.nd;

	return d;

}

ii forward(int cur,ii last) {

	int nx=get_nxt(last);

	if(greateq(mul({v[cur][nx],1},sub({nx,1},last)),req[cur])) {

		last=add(last,dvd(req[cur],{v[cur][nx],1}));

		return last;

	}

	req[cur]=sub(req[cur],mul({v[cur][nx],1},sub({nx,1},last)));
	last=add(last,sub({nx,1},last));

	//if(cur==1)  cerr<<"WTF\n"<<req[cur].st<<" "<<req[cur].nd<<"\n";

	int bas=nx+1,son=l;

	while(bas<=son) {

		if(greater(req[cur],{pre[cur][orta]-pre[cur][nx],1})) bas=orta+1;
		else son=orta-1;

	}

	last=add(last,{son-nx,1});
	req[cur]=sub(req[cur],{pre[cur][son]-pre[cur][nx],1});

	if(son==l) {last={l+1,1};return last;}

	ii fr=dvd(req[cur],{v[cur][bas],1});

	last=add(last,fr);

	return last;

}

void lets_try2() {

	for(int i=0;i<n;i++) {
	
		reverse(v[i]+1,v[i]+1+l);

		for(int j=1;j<=l;j++) pre[i][j]=pre[i][j-1]+v[i][j];

	}
	
	vector<int> has;

	for(int i=0;i<n;i++) has.pb(i);

	vector<int> ans;
	vector<ii> ab;

	ii cp={0,1};

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

		ii last={inf,1};
		int tut=-1;

		for(auto x:has) {

			ii lnw=forward(x,cp);

			req[x]=reqq[x];

			last=gmin(last,lnw);

			if(eq(last,lnw)) tut=x;

		}

		if(greater(last,{l,1})) {

			printf("-1");

			return ;

		}

		ans.pb(tut);

		has.erase(find(all(has),tut));

		cp=last;

		if(i<n-1) ab.pb(last);

	}

	reverse(all(ans));
	reverse(all(ab));

	for(auto& x:ab) x=sub({l,1},x);

	//printf("1");

	for(auto x:ab) printf("%lld %lld\n",x.st,x.nd);

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

}

void lets_try() {

	vector<int> has;

	for(int i=0;i<n;i++) has.pb(i);

	vector<int> ans;
	vector<ii> ab;

	ii cp={0,1};

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

		ii last={inf,1};
		int tut=-1;

		for(auto x:has) {

			ii lnw=forward(x,cp);

			req[x]=reqq[x];

			last=gmin(last,lnw);

			if(eq(last,lnw)) tut=x;

		}

		if(greater(last,{l,1})) {

			lets_try2();

			return ;

		}

		ans.pb(tut);

		//cerr<<"kes\n";

		//cerr<<tut<<" "<<last.st<<" "<<last.nd<<"\n";

		//cerr<<"kes\n\n";

		has.erase(find(all(has),tut));

		cp=last;

		if(i<n-1) ab.pb(last);

	}

//	printf("1");

	for(auto x:ab) printf("%lld %lld\n",x.st,x.nd);

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

}

int main() {

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

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

		for(int j=1;j<=l;j++) scanf("%d",v[i]+j),pre[i][j]=pre[i][j-1]+v[i][j];

		reqq[i]=req[i]={pre[i][l],n};
 
	}

	lets_try();

}

컴파일 시 표준 에러 (stderr) 메시지

naan.cpp: In function 'int main()':
naan.cpp:261: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:265:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int j=1;j<=l;j++) scanf("%d",v[i]+j),pre[i][j]=pre[i][j-1]+v[i][j];
                         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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