oj.uz

답안 #131646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
131646 2019-07-17T11:16:36 Z hamzqq9 Naan (JOI19_naan) C++14
29 / 100
 73 ms 13852 KB 
#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;
		
}

int get_nxt(ii a) {

	int 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();

}

Compilation message

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.0 / 5.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 0 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 3 ms 380 KB Output is correct
19 Correct 3 ms 504 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 380 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 3 ms 376 KB Output is correct
25 Correct 3 ms 504 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 3 ms 504 KB Output is correct
30 Correct 3 ms 376 KB Output is correct
31 Correct 3 ms 376 KB Output is correct
32 Correct 3 ms 504 KB Output is correct
33 Correct 3 ms 508 KB Output is correct
34 Correct 3 ms 504 KB Output is correct
35 Correct 3 ms 376 KB Output is correct
36 Correct 3 ms 504 KB Output is correct
37 Correct 3 ms 380 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 3 ms 376 KB Output is correct
40 Correct 3 ms 376 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 3 ms 376 KB Output is correct
43 Runtime error 73 ms 13852 KB Execution killed with signal 8 (could be triggered by violating memory limits)
44 Halted 0 ms 0 KB -