oj.uz

Submission #292523

# Submission time Handle Problem Language Result Execution time Memory
292523 2020-09-07T08:14:59 Z arnold518 Naan (JOI19_naan) C++14
29 / 100
 1211 ms 63992 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;

int N, L;
ll A[MAXN+10][MAXN+10];

struct Frac
{
	ll x, y;
	Frac() {}
	Frac(ll _x, ll _y)
	{
		x=_x; y=_y;
		norm();
	}
	void norm()
	{
		ll g=__gcd(x, y);
		x/=g; y/=g;
	}
};

bool operator < (Frac p, Frac q) { p.norm(); q.norm(); return p.y*q.x<q.y*p.x; }
bool operator > (Frac p, Frac q) { p.norm(); q.norm(); return p.y*q.x>q.y*p.x; }
bool operator == (Frac p, Frac q) { p.norm(); q.norm(); return p.y*q.x==q.y*p.x; }
bool operator <= (Frac p, Frac q) { p.norm(); q.norm(); return p.y*q.x<=q.y*p.x; }
bool operator >= (Frac p, Frac q) { p.norm(); q.norm(); return p.y*q.x>=q.y*p.x; }
Frac operator + (Frac p, Frac q)
{
	Frac ret;
	p.norm(); q.norm();
	ret.x=p.x*q.x;
	ret.y=p.y*q.x+q.y*p.x;
	ret.norm();
	return ret;
}
Frac operator - (Frac p, Frac q)
{
	Frac ret;
	p.norm(); q.norm();
	ret.x=p.x*q.x;
	ret.y=p.y*q.x-q.y*p.x;
	ret.norm();
	return ret;
}

Frac B[MAXN+10][MAXN+10];
bool vis[MAXN+10];
int ans[MAXN+10];

int main()
{
	scanf("%d%d", &N, &L);
	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=L; j++) scanf("%lld", &A[i][j]), A[i][j]+=A[i][j-1];
		for(int j=1, p=1; j<=N; j++)
		{
			for(; p<=L && A[i][p]*N<j*A[i][L]; p++);
			ll t=j*A[i][L]-N*A[i][p-1];
			B[i][j]=Frac(N*(A[i][p]-A[i][p-1]), t)+Frac(1, p-1);
			//printf("(%lld %lld !%d) ", B[i][j].x, B[i][j].y, p);
		}
		//printf("\n");
	}

	for(int i=1; i<=N; i++)
	{
		Frac t; int val=-1;
		for(int j=1; j<=N; j++)
		{
			if(vis[j]) continue;
			if(val==-1 || t>=B[j][i]) val=j, t=B[j][i];
		}
		if(i<N) printf("%lld %lld\n", t.y, t.x);
		ans[i]=val;
		vis[val]=true;
	}
	for(int i=1; i<=N; i++) printf("%d ", ans[i]); printf("\n");
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:85:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   85 |  for(int i=1; i<=N; i++) printf("%d ", ans[i]); printf("\n");
      |  ^~~
naan.cpp:85:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |  for(int i=1; i<=N; i++) printf("%d ", ans[i]); printf("\n");
      |                                                 ^~~~~~
naan.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  scanf("%d%d", &N, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~
naan.cpp:62:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |   for(int j=1; j<=L; j++) scanf("%lld", &A[i][j]), A[i][j]+=A[i][j-1];
      |                           ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 2 ms 520 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 2 ms 512 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 1 ms 512 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 512 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 2 ms 512 KB Output is correct
30 Correct 2 ms 512 KB Output is correct
31 Correct 2 ms 512 KB Output is correct
32 Correct 2 ms 512 KB Output is correct
33 Correct 2 ms 512 KB Output is correct
34 Correct 2 ms 520 KB Output is correct
35 Correct 2 ms 512 KB Output is correct
36 Correct 2 ms 512 KB Output is correct
37 Correct 2 ms 512 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 2 ms 512 KB Output is correct
40 Correct 1 ms 384 KB Output is correct
41 Correct 1 ms 384 KB Output is correct
42 Correct 2 ms 512 KB Output is correct
43 Correct 200 ms 13384 KB Output is correct
44 Incorrect 1211 ms 63992 KB X_i is not increasing
45 Halted 0 ms 0 KB -