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

191342 | 2020-01-14T17:54:38 Z | dolphingarlic | Naan (JOI19_naan) | C++14 | 1613 ms | 116600 KB |

#include <bits/stdc++.h> #define FOR(i, x, y) for (int i = x; i < y; i++) typedef long long ll; using namespace std; struct Rational { ll whole, num, den; Rational(ll num = 0): whole(num), num(0), den(1) {} Rational(ll whole, ll num, ll den): whole(whole), num(num), den(den) { norm(); } Rational(ll num, ll den): Rational(0, num, den) {} Rational& norm() { if (num > den) { whole += num / den; num %= den; } ll g = __gcd(num, den); num /= g; den /= g; return *this; } }; bool operator<(const Rational& u, const Rational& v) { if (u.whole == v.whole) return u.num * v.den < u.den * v.num; return u.whole < v.whole; } ostream& operator<<(ostream& cout, const Rational& u) { return cout << u.whole * u.den + u.num << ' ' << u.den; } Rational cut_places[2001][2001]; bool visited[2001]; int order[2001]; ll a[2001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, l; cin >> n >> l; FOR(i, 0, n) { ll sm = 0; FOR(j, 0, l) { cin >> a[j]; sm += a[j]; } ll curr = 0; int idx = 0; FOR(j, 1, n) { while ((curr + a[idx]) * n <= sm * j) curr += a[idx++]; ll res = sm * j - curr * n; cut_places[i][j] = Rational(idx, res, n * a[idx]); } } FOR(i, 1, n) { 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] = i; FOR(i, 1, n + 1) cout << order[i] + 1 << ' '; return 0; }

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

1 | Correct | 80 ms | 94328 KB | Output is correct |

2 | Correct | 82 ms | 94408 KB | Output is correct |

3 | Correct | 100 ms | 94456 KB | Output is correct |

4 | Correct | 96 ms | 94424 KB | Output is correct |

5 | Correct | 91 ms | 94432 KB | Output is correct |

6 | Correct | 81 ms | 94328 KB | Output is correct |

7 | Correct | 80 ms | 94456 KB | Output is correct |

8 | Correct | 79 ms | 94312 KB | Output is correct |

9 | Correct | 81 ms | 94400 KB | Output is correct |

10 | Correct | 85 ms | 94456 KB | Output is correct |

11 | Correct | 80 ms | 94456 KB | Output is correct |

12 | Correct | 86 ms | 94468 KB | Output is correct |

13 | Correct | 73 ms | 94328 KB | Output is correct |

14 | Correct | 89 ms | 94328 KB | Output is correct |

15 | Correct | 96 ms | 94328 KB | Output is correct |

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

1 | Correct | 80 ms | 94452 KB | Output is correct |

2 | Correct | 93 ms | 94456 KB | Output is correct |

3 | Correct | 104 ms | 94328 KB | Output is correct |

4 | Correct | 81 ms | 94328 KB | Output is correct |

5 | Correct | 79 ms | 94332 KB | Output is correct |

6 | Correct | 79 ms | 94328 KB | Output is correct |

7 | Correct | 80 ms | 94464 KB | Output is correct |

8 | Correct | 81 ms | 94456 KB | Output is correct |

9 | Correct | 80 ms | 94428 KB | Output is correct |

10 | Correct | 80 ms | 94328 KB | Output is correct |

11 | Correct | 80 ms | 94360 KB | Output is correct |

12 | Correct | 79 ms | 94456 KB | Output is correct |

13 | Correct | 80 ms | 94332 KB | Output is correct |

14 | Correct | 82 ms | 94456 KB | Output is correct |

15 | Correct | 80 ms | 94456 KB | Output is correct |

16 | Correct | 80 ms | 94456 KB | Output is correct |

17 | Correct | 80 ms | 94380 KB | Output is correct |

18 | Correct | 80 ms | 94456 KB | Output is correct |

19 | Correct | 80 ms | 94428 KB | Output is correct |

20 | Correct | 80 ms | 94328 KB | Output is correct |

21 | Correct | 80 ms | 94364 KB | Output is correct |

22 | Correct | 80 ms | 94328 KB | Output is correct |

23 | Correct | 79 ms | 94340 KB | Output is correct |

24 | Correct | 79 ms | 94328 KB | Output is correct |

25 | Correct | 80 ms | 94456 KB | Output is correct |

26 | Correct | 109 ms | 94328 KB | Output is correct |

27 | Correct | 82 ms | 94428 KB | Output is correct |

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

1 | Correct | 80 ms | 94328 KB | Output is correct |

2 | Correct | 82 ms | 94408 KB | Output is correct |

3 | Correct | 100 ms | 94456 KB | Output is correct |

4 | Correct | 96 ms | 94424 KB | Output is correct |

5 | Correct | 91 ms | 94432 KB | Output is correct |

6 | Correct | 81 ms | 94328 KB | Output is correct |

7 | Correct | 80 ms | 94456 KB | Output is correct |

8 | Correct | 79 ms | 94312 KB | Output is correct |

9 | Correct | 81 ms | 94400 KB | Output is correct |

10 | Correct | 85 ms | 94456 KB | Output is correct |

11 | Correct | 80 ms | 94456 KB | Output is correct |

12 | Correct | 86 ms | 94468 KB | Output is correct |

13 | Correct | 73 ms | 94328 KB | Output is correct |

14 | Correct | 89 ms | 94328 KB | Output is correct |

15 | Correct | 96 ms | 94328 KB | Output is correct |

16 | Correct | 80 ms | 94452 KB | Output is correct |

17 | Correct | 93 ms | 94456 KB | Output is correct |

18 | Correct | 104 ms | 94328 KB | Output is correct |

19 | Correct | 81 ms | 94328 KB | Output is correct |

20 | Correct | 79 ms | 94332 KB | Output is correct |

21 | Correct | 79 ms | 94328 KB | Output is correct |

22 | Correct | 80 ms | 94464 KB | Output is correct |

23 | Correct | 81 ms | 94456 KB | Output is correct |

24 | Correct | 80 ms | 94428 KB | Output is correct |

25 | Correct | 80 ms | 94328 KB | Output is correct |

26 | Correct | 80 ms | 94360 KB | Output is correct |

27 | Correct | 79 ms | 94456 KB | Output is correct |

28 | Correct | 80 ms | 94332 KB | Output is correct |

29 | Correct | 82 ms | 94456 KB | Output is correct |

30 | Correct | 80 ms | 94456 KB | Output is correct |

31 | Correct | 80 ms | 94456 KB | Output is correct |

32 | Correct | 80 ms | 94380 KB | Output is correct |

33 | Correct | 80 ms | 94456 KB | Output is correct |

34 | Correct | 80 ms | 94428 KB | Output is correct |

35 | Correct | 80 ms | 94328 KB | Output is correct |

36 | Correct | 80 ms | 94364 KB | Output is correct |

37 | Correct | 80 ms | 94328 KB | Output is correct |

38 | Correct | 79 ms | 94340 KB | Output is correct |

39 | Correct | 79 ms | 94328 KB | Output is correct |

40 | Correct | 80 ms | 94456 KB | Output is correct |

41 | Correct | 109 ms | 94328 KB | Output is correct |

42 | Correct | 82 ms | 94428 KB | Output is correct |

43 | Correct | 208 ms | 95960 KB | Output is correct |

44 | Correct | 876 ms | 104260 KB | Output is correct |

45 | Correct | 357 ms | 101828 KB | Output is correct |

46 | Correct | 109 ms | 95616 KB | Output is correct |

47 | Correct | 551 ms | 102516 KB | Output is correct |

48 | Correct | 1296 ms | 96184 KB | Output is correct |

49 | Correct | 333 ms | 95480 KB | Output is correct |

50 | Correct | 1507 ms | 99920 KB | Output is correct |

51 | Correct | 563 ms | 98224 KB | Output is correct |

52 | Correct | 1237 ms | 101440 KB | Output is correct |

53 | Correct | 1157 ms | 99276 KB | Output is correct |

54 | Correct | 79 ms | 94328 KB | Output is correct |

55 | Correct | 667 ms | 94840 KB | Output is correct |

56 | Correct | 708 ms | 98632 KB | Output is correct |

57 | Correct | 610 ms | 97728 KB | Output is correct |

58 | Correct | 1139 ms | 98268 KB | Output is correct |

59 | Correct | 593 ms | 98520 KB | Output is correct |

60 | Correct | 1333 ms | 116316 KB | Output is correct |

61 | Correct | 1380 ms | 116296 KB | Output is correct |

62 | Correct | 1584 ms | 116300 KB | Output is correct |

63 | Correct | 1453 ms | 116600 KB | Output is correct |

64 | Correct | 1395 ms | 116296 KB | Output is correct |

65 | Correct | 1613 ms | 103024 KB | Output is correct |

66 | Correct | 1602 ms | 103160 KB | Output is correct |

67 | Correct | 1396 ms | 103004 KB | Output is correct |

68 | Correct | 624 ms | 100344 KB | Output is correct |

69 | Correct | 544 ms | 102108 KB | Output is correct |

70 | Correct | 729 ms | 100828 KB | Output is correct |

71 | Correct | 883 ms | 105464 KB | Output is correct |