oj.uz

답안 #246720

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
246720 2020-07-10T02:11:16 Z luciocf Naan (JOI19_naan) C++14
29 / 100
 496 ms 55800 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

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

const int maxn = 2e3+10;

int a[maxn][maxn];
ll soma[maxn];

pii split[maxn][maxn];

bool mark[maxn];

bool menor(pii f1, pii f2)
{
	return f1.ff*f2.ss < f2.ff*f1.ss;
}

int main(void)
{
	int n, l;
	scanf("%d %d", &n, &l);

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= l; j++)
		{
			scanf("%d", &a[i][j]);

			soma[i] += 1ll*a[i][j];
		}
	}

	for (int i = 1; i <= n; i++)
	{
		int at = 1;
		ll s = 0;

		for (int j = 1; j < n; j++)
		{
			s += soma[i];

			while (at <= l && 1ll*a[i][at]*n <= s)
				s -= 1ll*a[i][at++]*n;

			ll g = __gcd(s + 1ll*(at-1)*a[i][at]*n, 1ll*a[i][at]*n);
			split[i][j] = {(s + 1ll*(at-1)*a[i][at]*n)/g, (1ll*a[i][at]*n)/g};
		}
	}

	vector<int> p;

	for (int i = 1; i < n; i++)
	{
		int ind = 0;

		for (int j = 1; j <= n; j++)
		{
			if (mark[j]) continue;

			if (!ind || menor(split[j][i], split[ind][i]))
				ind = j;
		}

		mark[ind] = 1;

		printf("%lld %lld\n", split[ind][i].ff, split[ind][i].ss);
		p.push_back(ind);
	}

	for (int i = 1; i <= n; i++)
		if (!mark[i])
			p.push_back(i);

	for (auto x: p)
		printf("%d ", x);
	printf("\n");
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:28: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:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 7 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 512 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 6 ms 512 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 6 ms 384 KB Output is correct
21 Correct 8 ms 384 KB Output is correct
22 Correct 6 ms 544 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 6 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 7 ms 360 KB Output is correct

Subtask #3
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 7 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 6 ms 512 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 6 ms 384 KB Output is correct
30 Correct 6 ms 384 KB Output is correct
31 Correct 6 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 6 ms 512 KB Output is correct
34 Correct 6 ms 384 KB Output is correct
35 Correct 6 ms 384 KB Output is correct
36 Correct 8 ms 384 KB Output is correct
37 Correct 6 ms 544 KB Output is correct
38 Correct 4 ms 384 KB Output is correct
39 Correct 6 ms 384 KB Output is correct
40 Correct 5 ms 384 KB Output is correct
41 Correct 5 ms 384 KB Output is correct
42 Correct 7 ms 360 KB Output is correct
43 Correct 94 ms 12408 KB Output is correct
44 Incorrect 496 ms 55800 KB X_i is not increasing
45 Halted 0 ms 0 KB -