oj.uz

Submission #123831

# Submission time Handle Problem Language Result Execution time Memory
123831 2019-07-02T07:41:30 Z 김현수(#3336) Naan (JOI19_naan) C++14
29 / 100
 434 ms 62916 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N = 2005;

ll n, m, s[N][N], ans[N];

bool dn[N];

struct frac {
	ll j, m;
	bool operator < (frac &T) {
		return j * T.m < T.j * m;
	}
} x[N][N];

frac get_border (ll I, ll A, ll B) {
	ll S = 0, E = m;
	while(S<E) {
		ll M = (S+E)/2+1;
		s[I][M] * B > A ? E = M-1 : S = M;
	}
	A -= s[I][S] * B;
	frac ret = {A, (s[I][S+1] - s[I][S]) * B};
	return {ret.j + ret.m * S, ret.m};
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++) {
		for(ll j=1;j<=m;j++) {
			scanf("%lld",&s[i][j]);
			s[i][j] += s[i][j-1];
		}
		s[i][m+1] = s[i][m] + 1;
		for(ll j=1;j<=n;j++) {
			x[i][j] = get_border(i, j*s[i][m], n);
		}
	}
	for(ll i=1;i<=n;i++) {
		ll I = -1;
		for(ll j=1;j<=n;j++) {
			if(dn[j]) continue;
			if(I == -1 || x[j][i] < x[I][i]) I = j;
		}
		ans[i] = I;
		dn[I] = true;
		if(i != n) printf("%lld %lld\n", x[I][i].j, x[I][i].m);
	}
	for(ll i=1;i<=n;i++) {
		printf("%lld ", ans[i]);
	}
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~
naan.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&s[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.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 2 ms 380 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 376 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 2 ms 380 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 2 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 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 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 504 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 376 KB Output is correct
15 Correct 3 ms 376 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 376 KB Output is correct
19 Correct 3 ms 376 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 504 KB Output is correct
25 Correct 3 ms 348 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 2 ms 380 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 376 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 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 3 ms 504 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 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 504 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 376 KB Output is correct
30 Correct 3 ms 376 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 376 KB Output is correct
34 Correct 3 ms 376 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 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 348 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 3 ms 376 KB Output is correct
43 Correct 73 ms 13240 KB Output is correct
44 Incorrect 434 ms 62916 KB X_i is not increasing
45 Halted 0 ms 0 KB -