oj.uz

Submission #123723

# Submission time Handle Problem Language Result Execution time Memory
123723 2019-07-02T05:37:21 Z 박상수(#3035) Naan (JOI19_naan) C++14
29 / 100
 301 ms 55772 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N, L;
int A[2020][2020];
pll P[2020][2020];
pll ans[2020];
int perm[2020];

int main() {
	scanf("%d%d", &N, &L);
	for(int i=1;i<=N;i++) for(int j=1;j<=L;j++) scanf("%d", A[i] + j);
	for(int i=1;i<=N;i++) {
		int sum = 0;
		for(int j=1;j<=L;j++) sum += A[i][j];
		int j = 0, now = 0;
		for(int k=1;k<=N;k++) {
			while(1) {
				if((ll)sum * k <= (ll)(now + A[i][j+1]) * N) {
					ll delta = (ll)sum * k - (ll)now * N;
					P[i][k] = pll(delta + (ll)A[i][j+1] * N * j, A[i][j+1] * N);
					break;
				}
				else ++j, now += A[i][j];
			}
		}
	}
	int chk[2020] = {};
	for(int i=1;i<=N;i++) {
		int f = -1;
		for(int j=1;j<=N;j++) if(chk[j] == 0) {
			if(f == -1) f = j;
			else {
				if(P[f][i].Fi * P[j][i].Se > P[j][i].Fi * P[f][i].Se) f = j;
			}
		}
		perm[i] = f;
		chk[f] = 1;
		ans[i] = P[f][i];
	}
	for(int i=1;i<N;i++) printf("%lld %lld\n", ans[i].Fi, ans[i].Se);
	for(int i=1;i<=N;i++) printf("%d ", perm[i]); puts("");
	return 0;
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:70:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i=1;i<=N;i++) printf("%d ", perm[i]); puts("");
  ^~~
naan.cpp:70:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int i=1;i<=N;i++) printf("%d ", perm[i]); puts("");
                                                ^~~~
naan.cpp:39: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:40:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) for(int j=1;j<=L;j++) scanf("%d", A[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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 380 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 3 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 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 3 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 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 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 3 ms 508 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 376 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 3 ms 504 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 384 KB Output is correct
26 Correct 2 ms 376 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 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 380 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 3 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 3 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 3 ms 504 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 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 376 KB Output is correct
31 Correct 3 ms 376 KB Output is correct
32 Correct 3 ms 508 KB Output is correct
33 Correct 3 ms 504 KB Output is correct
34 Correct 3 ms 504 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 504 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 3 ms 376 KB Output is correct
40 Correct 3 ms 384 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 3 ms 376 KB Output is correct
43 Correct 50 ms 12316 KB Output is correct
44 Incorrect 301 ms 55772 KB X_i is not increasing
45 Halted 0 ms 0 KB -