제출 #131582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131582		hamzqq9	Naan (JOI19_naan)	C++14	29 / 100	4003 ms	8552 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
using namespace std;
#define greater bos

struct result {

	bool ok;
	vector<ii> ab;

};

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;

}

int get_nxt(ii a) {

	int d=(a.st-a.nd+1)/a.nd+1;

	return d;

}

void forward(int cur,ii& last) {

	int nx=get_nxt(last);

	//cerr<<nx<<"\n";

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

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

		return ;

	}

	//cerr<<"GO ON\n";

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

	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;

	}

	//cerr<<"son : "<<son<<"\n";

	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 ;}

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

	last=add(last,fr);

}

result check(vector<int> p) {

	result res;

	res.ok=0;

	ii last={0,1};
	int cnt=0;

	for(int i:p) {

		forward(i,last);

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

		if(greater(last,{l,1})) return res;

		++cnt;

		if(cnt==n) last={l,1};

		else res.ab.pb(last);

	}

	res.ok=1;

	return res;

}

void brute() {

	vector<int> p;

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

	result ans;
	
	ans.ok=0;

	do {

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

		ans=check(p);

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

		if(ans.ok) break ;

		for(auto x:p) req[x]=reqq[x];

	} while(next_permutation(all(p)));

	if(!ans.ok) printf("-1");
	else {

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

		for(auto x:p) 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};
 
	}

	brute();

}

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

naan.cpp: In function 'int main()':
naan.cpp:198: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:202: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