oj.uz

Submission #123732

# Submission time Handle Problem Language Result Execution time Memory
123732 2019-07-02T05:46:57 Z 구재현(#3036) Naan (JOI19_naan) C++14
29 / 100
 49 ms 8480 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
using lint = long long;
using pi = pair<int, int>;

int n, m;
int a[MAXN][MAXN];

vector<pi> frac;
vector<int> who;

pi howLeft[MAXN][MAXN];
bool vis[MAXN];

auto cmp = [](pi a, pi b){
	return (__int128)a.first * b.second < (__int128) b.first * a.second;
};

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1; i<=n; i++){
		lint sum = 0;
		for(int j=1; j<=m; j++){
			sum += a[i][j];
		}
		lint curSum = 0;
		howLeft[i][0] = pi(0, 1);
		int ptr = 0;
		for(int j=1; j<n; j++){
			while(curSum + a[i][ptr+1] * n<= sum * j){
				curSum += a[i][++ptr] * n;
			}
			lint tmp = sum * j - curSum;
			auto frac = pi(tmp, a[i][ptr + 1] * n);
			frac.first += 1ll * ptr * n * a[i][ptr + 1];
			howLeft[i][j] = frac;
		}
		howLeft[i][n] = pi(m, 1);
	}
	for(int i=1; i<=n; i++){
		pi minv(m + 1, 1);
		int pos = 1;
		for(int j=1; j<=n; j++){
			if(!vis[j] && cmp(howLeft[j][i], minv)){
				minv = howLeft[j][i];
				pos = j;
			}
		}
		vis[pos] = 1;
		who.push_back(pos);
		if(i < n) frac.push_back(minv);
	}
	for(auto &i : frac) printf("%d %d\n", i.first, i.second);
	for(auto &i : who) printf("%d ", i);
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 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 376 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 376 KB Output is correct
15 Correct 2 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 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 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 3 ms 376 KB Output is correct
10 Correct 3 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 3 ms 376 KB Output is correct
15 Correct 3 ms 380 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 3 ms 380 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 376 KB Output is correct
22 Correct 3 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 2 ms 376 KB Output is correct
26 Correct 2 ms 424 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 380 KB Output is correct
2 Correct 2 ms 376 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 376 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 376 KB Output is correct
15 Correct 2 ms 376 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 380 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 376 KB Output is correct
26 Correct 2 ms 376 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 380 KB Output is correct
31 Correct 3 ms 376 KB Output is correct
32 Correct 3 ms 380 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 376 KB Output is correct
37 Correct 3 ms 376 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 3 ms 376 KB Output is correct
40 Correct 2 ms 376 KB Output is correct
41 Correct 2 ms 424 KB Output is correct
42 Correct 3 ms 376 KB Output is correct
43 Incorrect 49 ms 8480 KB Integer parameter [name=A_i] equals to -2024391405, violates the range [1, 2000000000000]
44 Halted 0 ms 0 KB -