oj.uz

Submission #131582

# Submission time Handle Problem Language Result Execution time Memory
131582 2019-07-17T10:01:43 Z hamzqq9 Naan (JOI19_naan) C++14
29 / 100
 4000 ms 8552 KB 
#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();

}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 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 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 416 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 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 3 ms 508 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 4 ms 508 KB Output is correct
15 Correct 4 ms 504 KB Output is correct
16 Correct 3 ms 504 KB Output is correct
17 Correct 3 ms 504 KB Output is correct
18 Correct 3 ms 504 KB Output is correct
19 Correct 3 ms 504 KB Output is correct
20 Correct 3 ms 504 KB Output is correct
21 Correct 3 ms 504 KB Output is correct
22 Correct 4 ms 504 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 3 ms 504 KB Output is correct
25 Correct 3 ms 504 KB Output is correct
26 Correct 3 ms 376 KB Output is correct
27 Correct 3 ms 504 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 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 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 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 3 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 3 ms 416 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 3 ms 376 KB Output is correct
23 Correct 3 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 3 ms 508 KB Output is correct
27 Correct 3 ms 376 KB Output is correct
28 Correct 3 ms 504 KB Output is correct
29 Correct 4 ms 508 KB Output is correct
30 Correct 4 ms 504 KB Output is correct
31 Correct 3 ms 504 KB Output is correct
32 Correct 3 ms 504 KB Output is correct
33 Correct 3 ms 504 KB Output is correct
34 Correct 3 ms 504 KB Output is correct
35 Correct 3 ms 504 KB Output is correct
36 Correct 3 ms 504 KB Output is correct
37 Correct 4 ms 504 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 3 ms 504 KB Output is correct
40 Correct 3 ms 504 KB Output is correct
41 Correct 3 ms 376 KB Output is correct
42 Correct 3 ms 504 KB Output is correct
43 Execution timed out 4003 ms 8552 KB Time limit exceeded
44 Halted 0 ms 0 KB -