oj.uz

Submission #123977

# Submission time Handle Problem Language Result Execution time Memory
123977 2019-07-02T10:21:39 Z imyujin Naan (JOI19_naan) C++14
29 / 100
 1025 ms 82844 KB 
#include<stdio.h>
#include<bitset>

using namespace std;

#define MAXN 2005
#define fi first
#define se second

typedef long long lint;
typedef pair<lint, lint> pll;

lint V[MAXN][MAXN];
lint Vsum[MAXN][MAXN];
pll X[MAXN][MAXN];
bitset<MAXN> chk;
int P[MAXN];

bool cmp(pll a, pll b) {
	return a.fi * b.se < a.se * b.fi;
}

lint ggcd(lint a, lint b) {
	if(a % b == 0) return b;
	return ggcd(b, a % b);
}

pll mkfrac(lint a, lint b) {
	lint g = ggcd(a, b);
	return make_pair(a / g, b / g);
}

int main() {
	int N, L;

	scanf("%d%d", &N, &L);
	for(int i = 0; i < N; i++) for(int j = 0; j < L; j++) scanf("%lld", &V[i][j]);

	for(int i = 0; i < N; i++) {
		Vsum[i][0] = V[i][0];
		for(int j = 1; j < L; j++) Vsum[i][j] = Vsum[i][j - 1] + V[i][j];
	}
	for(int i = 0; i < N; i++) for(int j = 1; j < N; j++) {
		int s = 0, e = L - 1;
		while(s < e) {
			int m = (s + e) / 2;
			//printf("i = %d, m = %d, Vsum[i][m] = %lld\n", i, m, Vsum[i][m]);
			if(Vsum[i][m] * N < Vsum[i][L - 1] * j) s = m + 1;
			else e = m;
		}
		pll left = make_pair(Vsum[i][s] * N - Vsum[i][L - 1] * j, N * V[i][s]);
		X[i][j] = mkfrac((s + 1) * N * V[i][s] - left.fi, N * V[i][s]);
		//printf("i = %d, j = %d, s = %d, left = (%lld, %lld), X[i][j] = (%lld, %lld)\n", i, j, s, left.fi, left.se, X[i][j].fi, X[i][j].se);
	}

	for(int i = 1; i < N; i++) {
		int mn = -1;
		for(int j = 0; j < N; j++) if(!chk[j]) {
			if(mn == - 1 || cmp(X[j][i], X[mn][i])) mn = j;
		}
		printf("%lld %lld\n", X[mn][i].fi, X[mn][i].se);
		chk[mn] = true;
		P[i] = mn;
	}
	for(int i = 1; i < N; i++) printf("%d ", P[i] + 1);
	for(int i = 0; i < N; i++) if(!chk[i]) printf("%d", i + 1);

	return 0;
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:36: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:37:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N; i++) for(int j = 0; j < L; j++) scanf("%lld", &V[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 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 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 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 380 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 2 ms 504 KB Output is correct
3 Correct 3 ms 504 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 632 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 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 508 KB Output is correct
16 Correct 3 ms 492 KB Output is correct
17 Correct 3 ms 632 KB Output is correct
18 Correct 3 ms 504 KB Output is correct
19 Correct 3 ms 632 KB Output is correct
20 Correct 3 ms 524 KB Output is correct
21 Correct 3 ms 632 KB Output is correct
22 Correct 3 ms 632 KB Output is correct
23 Correct 2 ms 380 KB Output is correct
24 Correct 3 ms 504 KB Output is correct
25 Correct 3 ms 504 KB Output is correct
26 Correct 2 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 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 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 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 380 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 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 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 504 KB Output is correct
25 Correct 3 ms 632 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 504 KB Output is correct
29 Correct 3 ms 504 KB Output is correct
30 Correct 3 ms 508 KB Output is correct
31 Correct 3 ms 492 KB Output is correct
32 Correct 3 ms 632 KB Output is correct
33 Correct 3 ms 504 KB Output is correct
34 Correct 3 ms 632 KB Output is correct
35 Correct 3 ms 524 KB Output is correct
36 Correct 3 ms 632 KB Output is correct
37 Correct 3 ms 632 KB Output is correct
38 Correct 2 ms 380 KB Output is correct
39 Correct 3 ms 504 KB Output is correct
40 Correct 3 ms 504 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 3 ms 504 KB Output is correct
43 Correct 171 ms 17756 KB Output is correct
44 Incorrect 1025 ms 82844 KB X_i is not increasing
45 Halted 0 ms 0 KB -