# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

191338 | 2020-01-14T17:16:37 Z | dolphingarlic | Naan (JOI19_naan) | C++14 | 2391 ms | 64612 KB |

#include <bits/stdc++.h> #define FOR(i, x, y) for (ll i = x; i < y; i++) typedef long long ll; using namespace std; ll gcd(ll A, ll B) { return (B ? gcd(B, A % B) : A); } struct Rational { ll x, y; // x/y Rational(ll num = 1, ll den = 1) { ll g = gcd(num, den); x = num / g; y = den / g; } Rational operator+(Rational B) { return Rational(x * B.y + B.x * y, y * B.y); } Rational operator-(Rational B) { return Rational(x * B.y - B.x * y, y * B.y); } Rational operator*(Rational B) { return Rational(x * B.x, y * B.y); } }; bool operator<(Rational A, Rational B) { return A.x * B.y < A.y * B.x; } ostream& operator<<(ostream& os, const Rational& A) { os << A.x << ' ' << A.y; return os; } Rational cut_places[2001][2001]; bool visited[2001]; ll order[2001], a[2001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll n, l; cin >> n >> l; FOR(i, 0, n) { ll sm = 0; FOR(j, 0, l) { cin >> a[j]; sm += a[j]; } Rational curr = Rational(0), target = Rational(sm, n); int idx = 0; FOR(j, 0, l) { while (target < curr + Rational(a[j])) { Rational offset = target - curr; cut_places[i][idx++] = Rational(j) + offset * Rational(1, a[j]); target = target + Rational(sm, n); // Error here // assert(Rational(0) < cut_places[i][idx - 1]); // assert(Rational(0) < offset); // assert(Rational(0) < target); } curr = curr + Rational(a[j]); } } FOR(i, 0, n - 1) { Rational earliest = Rational(1000000000); FOR(j, 0, n) if (!visited[j] && cut_places[j][i] < earliest) { earliest = cut_places[j][i]; order[i] = j; } cout << earliest << '\n'; visited[order[i]] = true; } FOR(i, 0, n) if (!visited[i]) order[n - 1] = i; FOR(i, 0, n) cout << order[i] + 1 << ' '; return 0; }

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 48 ms | 63068 KB | Output is correct |

2 | Correct | 55 ms | 63080 KB | Output is correct |

3 | Correct | 55 ms | 63096 KB | Output is correct |

4 | Correct | 53 ms | 63088 KB | Output is correct |

5 | Correct | 53 ms | 62968 KB | Output is correct |

6 | Correct | 54 ms | 62972 KB | Output is correct |

7 | Correct | 54 ms | 63148 KB | Output is correct |

8 | Correct | 55 ms | 63224 KB | Output is correct |

9 | Correct | 52 ms | 63096 KB | Output is correct |

10 | Correct | 54 ms | 62968 KB | Output is correct |

11 | Correct | 54 ms | 63096 KB | Output is correct |

12 | Correct | 54 ms | 63176 KB | Output is correct |

13 | Correct | 54 ms | 63096 KB | Output is correct |

14 | Correct | 54 ms | 63096 KB | Output is correct |

15 | Correct | 52 ms | 63096 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 53 ms | 62968 KB | Output is correct |

2 | Correct | 56 ms | 63052 KB | Output is correct |

3 | Correct | 56 ms | 63096 KB | Output is correct |

4 | Correct | 52 ms | 63096 KB | Output is correct |

5 | Correct | 54 ms | 63016 KB | Output is correct |

6 | Correct | 55 ms | 63100 KB | Output is correct |

7 | Correct | 55 ms | 63096 KB | Output is correct |

8 | Correct | 53 ms | 63096 KB | Output is correct |

9 | Correct | 55 ms | 63096 KB | Output is correct |

10 | Correct | 54 ms | 63108 KB | Output is correct |

11 | Correct | 52 ms | 63096 KB | Output is correct |

12 | Correct | 54 ms | 62968 KB | Output is correct |

13 | Correct | 54 ms | 63096 KB | Output is correct |

14 | Correct | 54 ms | 63008 KB | Output is correct |

15 | Correct | 54 ms | 63096 KB | Output is correct |

16 | Correct | 54 ms | 63056 KB | Output is correct |

17 | Correct | 54 ms | 63096 KB | Output is correct |

18 | Correct | 55 ms | 63028 KB | Output is correct |

19 | Correct | 59 ms | 63224 KB | Output is correct |

20 | Correct | 53 ms | 63096 KB | Output is correct |

21 | Correct | 54 ms | 63096 KB | Output is correct |

22 | Correct | 54 ms | 63016 KB | Output is correct |

23 | Correct | 54 ms | 63120 KB | Output is correct |

24 | Correct | 55 ms | 63224 KB | Output is correct |

25 | Correct | 54 ms | 63096 KB | Output is correct |

26 | Correct | 56 ms | 63060 KB | Output is correct |

27 | Correct | 54 ms | 63096 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 48 ms | 63068 KB | Output is correct |

2 | Correct | 55 ms | 63080 KB | Output is correct |

3 | Correct | 55 ms | 63096 KB | Output is correct |

4 | Correct | 53 ms | 63088 KB | Output is correct |

5 | Correct | 53 ms | 62968 KB | Output is correct |

6 | Correct | 54 ms | 62972 KB | Output is correct |

7 | Correct | 54 ms | 63148 KB | Output is correct |

8 | Correct | 55 ms | 63224 KB | Output is correct |

9 | Correct | 52 ms | 63096 KB | Output is correct |

10 | Correct | 54 ms | 62968 KB | Output is correct |

11 | Correct | 54 ms | 63096 KB | Output is correct |

12 | Correct | 54 ms | 63176 KB | Output is correct |

13 | Correct | 54 ms | 63096 KB | Output is correct |

14 | Correct | 54 ms | 63096 KB | Output is correct |

15 | Correct | 52 ms | 63096 KB | Output is correct |

16 | Correct | 53 ms | 62968 KB | Output is correct |

17 | Correct | 56 ms | 63052 KB | Output is correct |

18 | Correct | 56 ms | 63096 KB | Output is correct |

19 | Correct | 52 ms | 63096 KB | Output is correct |

20 | Correct | 54 ms | 63016 KB | Output is correct |

21 | Correct | 55 ms | 63100 KB | Output is correct |

22 | Correct | 55 ms | 63096 KB | Output is correct |

23 | Correct | 53 ms | 63096 KB | Output is correct |

24 | Correct | 55 ms | 63096 KB | Output is correct |

25 | Correct | 54 ms | 63108 KB | Output is correct |

26 | Correct | 52 ms | 63096 KB | Output is correct |

27 | Correct | 54 ms | 62968 KB | Output is correct |

28 | Correct | 54 ms | 63096 KB | Output is correct |

29 | Correct | 54 ms | 63008 KB | Output is correct |

30 | Correct | 54 ms | 63096 KB | Output is correct |

31 | Correct | 54 ms | 63056 KB | Output is correct |

32 | Correct | 54 ms | 63096 KB | Output is correct |

33 | Correct | 55 ms | 63028 KB | Output is correct |

34 | Correct | 59 ms | 63224 KB | Output is correct |

35 | Correct | 53 ms | 63096 KB | Output is correct |

36 | Correct | 54 ms | 63096 KB | Output is correct |

37 | Correct | 54 ms | 63016 KB | Output is correct |

38 | Correct | 54 ms | 63120 KB | Output is correct |

39 | Correct | 55 ms | 63224 KB | Output is correct |

40 | Correct | 54 ms | 63096 KB | Output is correct |

41 | Correct | 56 ms | 63060 KB | Output is correct |

42 | Correct | 54 ms | 63096 KB | Output is correct |

43 | Correct | 440 ms | 64612 KB | Output is correct |

44 | Incorrect | 2391 ms | 64348 KB | X_i is not increasing |

45 | Halted | 0 ms | 0 KB | - |