oj.uz

Submission #171650

# Submission time Handle Problem Language Result Execution time Memory
171650 2019-12-29T13:38:51 Z dennisstar Naan (JOI19_naan) C++11
29 / 100
 633 ms 79976 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;

int N, L;
int chk[2010];
ll V[2010][2010], S[2010];
vector<pll> ar[2010];
vector<pair<pll, int> > VP[2010];
vim ans;

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

int main() {
	scanf("%d %d", &N, &L);
	for (int i=1; i<=N; i++) for (int j=1; j<=L; j++) {
		scanf("%lld", &V[i][j]);
		V[i][j]*=N;
		S[i]+=V[i][j];
	}
	ll s;
	for (int i=1; i<=N; i++) {
		s=0;
		ar[i].push_back({0,1});
		for (int j=1, k=1; j<=L; j++) {
			s+=V[i][j];
			while (k<=N && k*(S[i]/N)<=s) {
				ar[i].push_back({(j-1)*V[i][j]+k*(S[i]/N)-(s-V[i][j]) , V[i][j]});
				k++;
			}
		}
		ar[i].push_back({L, 1});
	}
	pll lst={0, 1};
	for (int i=0; i<N; i++) {
		for (int j=1; j<=N; j++) {
			if (chk[j]) continue;
			int lb=lower_bound(all(ar[j]), lst, cmp)-ar[j].begin();
			VP[i].push_back({ar[j][lb+1], j});
		}
		sort(all(VP[i]), cmp1);
		if (i!=N-1) printf("%lld %lld\n", VP[i][0].fi.fi, VP[i][0].fi.se);
		ans.push_back(VP[i][0].se);
		chk[VP[i][0].se]=1;
		lst=VP[i][0].fi;
	}
	for (int i:ans) printf("%d ", i);
	puts("");
	return 0;
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:25: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:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 504 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 3 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 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 508 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 3 ms 504 KB Output is correct
17 Correct 4 ms 504 KB Output is correct
18 Correct 3 ms 504 KB Output is correct
19 Correct 15 ms 504 KB Output is correct
20 Correct 3 ms 504 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 504 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 504 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 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 3 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 3 ms 504 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 504 KB Output is correct
24 Correct 3 ms 504 KB Output is correct
25 Correct 3 ms 504 KB Output is correct
26 Correct 3 ms 504 KB Output is correct
27 Correct 2 ms 508 KB Output is correct
28 Correct 3 ms 504 KB Output is correct
29 Correct 3 ms 504 KB Output is correct
30 Correct 3 ms 504 KB Output is correct
31 Correct 3 ms 504 KB Output is correct
32 Correct 4 ms 504 KB Output is correct
33 Correct 3 ms 504 KB Output is correct
34 Correct 15 ms 504 KB Output is correct
35 Correct 3 ms 504 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 504 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 504 KB Output is correct
42 Correct 3 ms 504 KB Output is correct
43 Correct 94 ms 17628 KB Output is correct
44 Incorrect 633 ms 79976 KB X_i is not increasing
45 Halted 0 ms 0 KB -