oj.uz

Submission #131608

# Submission time Handle Problem Language Result Execution time Memory
131608 2019-07-17T10:23:57 Z hamzqq9 Naan (JOI19_naan) C++14
24 / 100
 3 ms 504 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
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+1)/a.nd+1;

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

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

	for(auto x:ab) printf("%d %d\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);

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

		cp=last;

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

	}

	for(auto x:ab) printf("%d %d\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_try2();

}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:248: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:252: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 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 Incorrect 2 ms 376 KB Integer parameter [name=A_i] equals to -1, violates the range [1, 2000000000000]
6 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 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 Incorrect 2 ms 376 KB Integer parameter [name=A_i] equals to -1, violates the range [1, 2000000000000]
6 Halted 0 ms 0 KB -