oj.uz

Submission #153005

# Submission time Handle Problem Language Result Execution time Memory
153005 2019-09-11T09:38:36 Z oolimry Naan (JOI19_naan) C++14
29 / 100
 140 ms 4420 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, long long> ii;
bool great(ii a, ii b){
	long long wa = a.first / a.second;
	long long wb = b.first / b.second;
	if(wa == wb){
		a.first /= a.second, b.first /= b.second;
		return a.first * b.second < a.second * b.first;
	}
	return wa < wb; //is b greater than a
	
}
int main(){
	//freopen("i.txt","r",stdin);
	cin.tie(0);
	
	long long n, l;
	cin >> n >> l;
	
	long long arr[n][l];
	long long sums[n];
	fill(sums,sums+n,0);
	for(long long i = 0;i < n;i++)
		for(long long j = 0;j < l;j++){
			cin >> arr[i][j];
			sums[i] += arr[i][j];
			arr[i][j] *= n;
		}
	long long pre[n][l];
	for(long long i = 0;i < n;i++)
		for(long long j = 0;j < l;j++){
			pre[i][j] = arr[i][j];
			if(j != 0) pre[i][j] += pre[i][j-1];
		}
	
	bool used[n];
	fill(used,used+n,false);
	vector<long long> order;
	
	for(long long r = 0;r < n;r++){
		ii minfrac = ii(102344213,1);
		long long mini;
		for(long long i = 0;i < n;i++){
			if(used[i]) continue;	
			
			long long need = (r+1) * sums[i];
			long long x = upper_bound(pre[i],pre[i]+l,need) - pre[i];
			
			ii frac;
			frac.second = arr[i][x];
			frac.first = need;
			if(x != 0) frac.first -= pre[i][x-1];
			frac.first += x * frac.second;
			
			if(great(frac,minfrac)){
				minfrac = frac;
				mini = i;
			}
		}
		if(r != n-1) cout << minfrac.first << " " << minfrac.second << "\n";
		used[mini] = true;
		order.push_back(mini);
	}
	
	for(int i = 0;i < n;i++){
		cout << order[i] + 1 << " ";
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 4 ms 376 KB Output is correct
13 Correct 4 ms 376 KB Output is correct
14 Correct 4 ms 380 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 4 ms 376 KB Output is correct
19 Correct 5 ms 504 KB Output is correct
20 Correct 6 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 3 ms 376 KB Output is correct
24 Correct 5 ms 504 KB Output is correct
25 Correct 4 ms 504 KB Output is correct
26 Correct 3 ms 376 KB Output is correct
27 Correct 2 ms 256 KB Output is correct
28 Correct 3 ms 376 KB Output is correct
29 Correct 4 ms 504 KB Output is correct
30 Correct 4 ms 376 KB Output is correct
31 Correct 5 ms 504 KB Output is correct
32 Correct 4 ms 504 KB Output is correct
33 Correct 5 ms 504 KB Output is correct
34 Correct 5 ms 504 KB Output is correct
35 Correct 4 ms 504 KB Output is correct
36 Correct 5 ms 504 KB Output is correct
37 Correct 5 ms 504 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 4 ms 504 KB Output is correct
40 Correct 4 ms 376 KB Output is correct
41 Correct 3 ms 380 KB Output is correct
42 Correct 4 ms 504 KB Output is correct
43 Incorrect 140 ms 4420 KB X_i is not increasing
44 Halted 0 ms 0 KB -