QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112056#6561. Fail FastNyaanWA 108ms21432kbC++1714.0kb2023-06-09 17:29:132023-06-09 17:29:16

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-09 17:29:16]
  • 评测
  • 测评结果:WA
  • 用时:108ms
  • 内存:21432kb
  • [2023-06-09 17:29:13]
  • 提交

answer

/**
 * date   : 2023-06-09 18:29:02
 * author : Nyaan
 */

#define NDEBUG

using namespace std;

// intrinstic
#include <immintrin.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

// utility

namespace Nyaan {
using ll = long long;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;

template <typename T>
using V = vector<T>;
template <typename T>
using VV = vector<vector<T>>;
using vi = vector<int>;
using vl = vector<long long>;
using vd = V<double>;
using vs = V<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;

template <typename T, typename U>
struct P : pair<T, U> {
  template <typename... Args>
  P(Args... args) : pair<T, U>(args...) {}

  using pair<T, U>::first;
  using pair<T, U>::second;

  P &operator+=(const P &r) {
    first += r.first;
    second += r.second;
    return *this;
  }
  P &operator-=(const P &r) {
    first -= r.first;
    second -= r.second;
    return *this;
  }
  P &operator*=(const P &r) {
    first *= r.first;
    second *= r.second;
    return *this;
  }
  template <typename S>
  P &operator*=(const S &r) {
    first *= r, second *= r;
    return *this;
  }
  P operator+(const P &r) const { return P(*this) += r; }
  P operator-(const P &r) const { return P(*this) -= r; }
  P operator*(const P &r) const { return P(*this) *= r; }
  template <typename S>
  P operator*(const S &r) const {
    return P(*this) *= r;
  }
  P operator-() const { return P{-first, -second}; }
};

using pl = P<ll, ll>;
using pi = P<int, int>;
using vp = V<pl>;

constexpr int inf = 1001001001;
constexpr long long infLL = 4004004004004004004LL;

template <typename T>
int sz(const T &t) {
  return t.size();
}

template <typename T, typename U>
inline bool amin(T &x, U y) {
  return (y < x) ? (x = y, true) : false;
}
template <typename T, typename U>
inline bool amax(T &x, U y) {
  return (x < y) ? (x = y, true) : false;
}

template <typename T>
inline T Max(const vector<T> &v) {
  return *max_element(begin(v), end(v));
}
template <typename T>
inline T Min(const vector<T> &v) {
  return *min_element(begin(v), end(v));
}
template <typename T>
inline long long Sum(const vector<T> &v) {
  return accumulate(begin(v), end(v), 0LL);
}

template <typename T>
int lb(const vector<T> &v, const T &a) {
  return lower_bound(begin(v), end(v), a) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, const T &a) {
  return upper_bound(begin(v), end(v), a) - begin(v);
}

constexpr long long TEN(int n) {
  long long ret = 1, x = 10;
  for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1);
  return ret;
}

template <typename T, typename U>
pair<T, U> mkp(const T &t, const U &u) {
  return make_pair(t, u);
}

template <typename T>
vector<T> mkrui(const vector<T> &v, bool rev = false) {
  vector<T> ret(v.size() + 1);
  if (rev) {
    for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1];
  } else {
    for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];
  }
  return ret;
};

template <typename T>
vector<T> mkuni(const vector<T> &v) {
  vector<T> ret(v);
  sort(ret.begin(), ret.end());
  ret.erase(unique(ret.begin(), ret.end()), ret.end());
  return ret;
}

template <typename F>
vector<int> mkord(int N,F f) {
  vector<int> ord(N);
  iota(begin(ord), end(ord), 0);
  sort(begin(ord), end(ord), f);
  return ord;
}

template <typename T>
vector<int> mkinv(vector<T> &v) {
  int max_val = *max_element(begin(v), end(v));
  vector<int> inv(max_val + 1, -1);
  for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i;
  return inv;
}

vector<int> mkiota(int n) {
  vector<int> ret(n);
  iota(begin(ret), end(ret), 0);
  return ret;
}

template <typename T>
T mkrev(const T &v) {
  T w{v};
  reverse(begin(w), end(w));
  return w;
}

template <typename T>
bool nxp(vector<T> &v) {
  return next_permutation(begin(v), end(v));
}

template <typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

}  // namespace Nyaan


// bit operation

namespace Nyaan {
__attribute__((target("popcnt"))) inline int popcnt(const u64 &a) {
  return _mm_popcnt_u64(a);
}
inline int lsb(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }
inline int ctz(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }
inline int msb(const u64 &a) { return a ? 63 - __builtin_clzll(a) : -1; }
template <typename T>
inline int gbit(const T &a, int i) {
  return (a >> i) & 1;
}
template <typename T>
inline void sbit(T &a, int i, bool b) {
  if (gbit(a, i) != b) a ^= T(1) << i;
}
constexpr long long PW(int n) { return 1LL << n; }
constexpr long long MSK(int n) { return (1LL << n) - 1; }
}  // namespace Nyaan


// inout

namespace Nyaan {

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.first << " " << p.second;
  return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  int s = (int)v.size();
  for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
  return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &x : v) is >> x;
  return is;
}

istream &operator>>(istream &is, __int128_t &x) {
  string S;
  is >> S;
  x = 0;
  int flag = 0;
  for (auto &c : S) {
    if (c == '-') {
      flag = true;
      continue;
    }
    x *= 10;
    x += c - '0';
  }
  if (flag) x = -x;
  return is;
}

istream &operator>>(istream &is, __uint128_t &x) {
  string S;
  is >> S;
  x = 0;
  for (auto &c : S) {
    x *= 10;
    x += c - '0';
  }
  return is;
}

ostream &operator<<(ostream &os, __int128_t x) {
  if (x == 0) return os << 0;
  if (x < 0) os << '-', x = -x;
  string S;
  while (x) S.push_back('0' + x % 10), x /= 10;
  reverse(begin(S), end(S));
  return os << S;
}
ostream &operator<<(ostream &os, __uint128_t x) {
  if (x == 0) return os << 0;
  string S;
  while (x) S.push_back('0' + x % 10), x /= 10;
  reverse(begin(S), end(S));
  return os << S;
}

void in() {}
template <typename T, class... U>
void in(T &t, U &...u) {
  cin >> t;
  in(u...);
}

void out() { cout << "\n"; }
template <typename T, class... U, char sep = ' '>
void out(const T &t, const U &...u) {
  cout << t;
  if (sizeof...(u)) cout << sep;
  out(u...);
}

struct IoSetupNya {
  IoSetupNya() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(7);
  }
} iosetupnya;

}  // namespace Nyaan


// debug


#ifdef NyaanDebug
#define trc(...) (void(0))
#else
#define trc(...) (void(0))
#endif

#ifdef NyaanLocal
#define trc2(...) (void(0))
#else
#define trc2(...) (void(0))
#endif


// macro

#define each(x, v) for (auto&& x : v)
#define each2(x, y, v) for (auto&& [x, y] : v)
#define all(v) (v).begin(), (v).end()
#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)
#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)
#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)
#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)
#define reg(i, a, b) for (long long i = (a); i < (b); i++)
#define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--)
#define fi first
#define se second
#define ini(...)   \
  int __VA_ARGS__; \
  in(__VA_ARGS__)
#define inl(...)         \
  long long __VA_ARGS__; \
  in(__VA_ARGS__)
#define ins(...)      \
  string __VA_ARGS__; \
  in(__VA_ARGS__)
#define in2(s, t)                           \
  for (int i = 0; i < (int)s.size(); i++) { \
    in(s[i], t[i]);                         \
  }
#define in3(s, t, u)                        \
  for (int i = 0; i < (int)s.size(); i++) { \
    in(s[i], t[i], u[i]);                   \
  }
#define in4(s, t, u, v)                     \
  for (int i = 0; i < (int)s.size(); i++) { \
    in(s[i], t[i], u[i], v[i]);             \
  }
#define die(...)             \
  do {                       \
    Nyaan::out(__VA_ARGS__); \
    return;                  \
  } while (0)


namespace Nyaan {
void solve();
}
int main() { Nyaan::solve(); }


//


struct UnionFind {
  vector<int> data;
  UnionFind(int N) : data(N, -1) {}

  int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); }

  int unite(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  // f ... merge function
  template<typename F>
  int unite(int x, int y,const F &f) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    f(x, y);
    return true;
  }

  int size(int k) { return -data[find(k)]; }

  int same(int x, int y) { return find(x) == find(y); }
};

/**
 * @brief Union Find(Disjoint Set Union)
 * @docs docs/data-structure/union-find.md
 */


//












namespace atcoder {
namespace internal {

template <class E> struct csr {
    std::vector<int> start;
    std::vector<E> elist;
    csr(int n, const std::vector<std::pair<int, E>>& edges)
        : start(n + 1), elist(edges.size()) {
        for (auto e : edges) {
            start[e.first + 1]++;
        }
        for (int i = 1; i <= n; i++) {
            start[i] += start[i - 1];
        }
        auto counter = start;
        for (auto e : edges) {
            elist[counter[e.first]++] = e.second;
        }
    }
};

}  // namespace internal

}  // namespace atcoder



namespace atcoder {
namespace internal {

// Reference:
// R. Tarjan,
// Depth-First Search and Linear Graph Algorithms
struct scc_graph {
  public:
    scc_graph(int n) : _n(n) {}

    int num_vertices() { return _n; }

    void add_edge(int from, int to) { edges.push_back({from, {to}}); }

    // @return pair of (# of scc, scc id)
    std::pair<int, std::vector<int>> scc_ids() {
        auto g = csr<edge>(_n, edges);
        int now_ord = 0, group_num = 0;
        std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
        visited.reserve(_n);
        auto dfs = [&](auto self, int v) -> void {
            low[v] = ord[v] = now_ord++;
            visited.push_back(v);
            for (int i = g.start[v]; i < g.start[v + 1]; i++) {
                auto to = g.elist[i].to;
                if (ord[to] == -1) {
                    self(self, to);
                    low[v] = std::min(low[v], low[to]);
                } else {
                    low[v] = std::min(low[v], ord[to]);
                }
            }
            if (low[v] == ord[v]) {
                while (true) {
                    int u = visited.back();
                    visited.pop_back();
                    ord[u] = _n;
                    ids[u] = group_num;
                    if (u == v) break;
                }
                group_num++;
            }
        };
        for (int i = 0; i < _n; i++) {
            if (ord[i] == -1) dfs(dfs, i);
        }
        for (auto& x : ids) {
            x = group_num - 1 - x;
        }
        return {group_num, ids};
    }

    std::vector<std::vector<int>> scc() {
        auto ids = scc_ids();
        int group_num = ids.first;
        std::vector<int> counts(group_num);
        for (auto x : ids.second) counts[x]++;
        std::vector<std::vector<int>> groups(ids.first);
        for (int i = 0; i < group_num; i++) {
            groups[i].reserve(counts[i]);
        }
        for (int i = 0; i < _n; i++) {
            groups[ids.second[i]].push_back(i);
        }
        return groups;
    }

  private:
    int _n;
    struct edge {
        int to;
    };
    std::vector<std::pair<int, edge>> edges;
};

}  // namespace internal

}  // namespace atcoder



namespace atcoder {

struct scc_graph {
  public:
    scc_graph() : internal(0) {}
    scc_graph(int n) : internal(n) {}

    void add_edge(int from, int to) {
        int n = internal.num_vertices();
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        internal.add_edge(from, to);
    }

    std::vector<std::vector<int>> scc() { return internal.scc(); }

  private:
    internal::scc_graph internal;
};

}  // namespace atcoder



using namespace Nyaan;

using Real = long double;
using pd = pair<Real, Real>;
Real cost(pd a) { return a.first / (1.0 - a.second); }
pd merge(pd a, pd b) {
  Real x = a.se * b.se;
  return {a.fi + a.se * b.fi, x};
};

void q() {
  inl(N);

  vi par(N, -1);
  V<double> c(N), p(N);

  rep(i, N) {
    int d;
    in(c[i], p[i], d);
    par[i] = d - 1;
  }

  minpq<pair<double, int>> Q;
  UnionFind uf(N);
  V<pd> dp(N);

  vi vis(N), pushed(N);
  vvi h(N);
  vi ans;
  vi lowest = mkiota(N);

  rep(i, N) {
    dp[i] = pd{c[i], p[i]};
    Q.emplace(cost(dp[i]), i);
  }

  auto dfs = [&](auto rc, int cc) -> void {
    ans.push_back(cc);
    pushed[cc] = 1;
    for (auto& d : h[cc]) rc(rc, d);
  };
  while (Q.size()) {
    auto [cv, v] = Q.top();
    Q.pop();
    if (vis[v]) continue;
    vis[v] = 1;

    if (par[v] != -1) {
      int u = lowest[par[v]];

      dp[u] = merge(dp[u], dp[v]);
      uf.unite(u, v, [&](int x, int y) { lowest[y] = lowest[x] = u; });

      Q.emplace(cost(dp[u]), u);
      if (pushed[par[v]]) {
        dfs(dfs, v);
      } else {
        h[par[v]].push_back(v);
      }
    } else {
      dfs(dfs, v);
    }
  }

  each(x, ans) out(x + 1);
}

void Nyaan::solve() {
  int t = 1;
  // in(t);
  while (t--) q();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3484kb

input:

4
100 0.5 0
200 0.1 1
10 0.5 2
10 0.9 0

output:

4
1
2
3

result:

ok correct

Test #2:

score: 0
Accepted
time: 2ms
memory: 3504kb

input:

4
84 0.716 0
91 0.115 0
19 0.640 1
103 0.455 0

output:

2
1
3
4

result:

ok correct

Test #3:

score: 0
Accepted
time: 2ms
memory: 3664kb

input:

10
18 0.574073 0
13 0.540309 0
13 0.539018 2
12 0.572910 2
15 0.570616 4
16 0.510215 3
17 0.504083 5
19 0.539297 1
19 0.577271 7
10 0.578346 1

output:

2
4
3
6
5
7
1
10
8
9

result:

ok correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

20
93 0.093030 0
53 0.056639 0
39 0.021549 0
48 0.069268 3
58 0.009572 4
22 0.015083 1
27 0.024351 5
68 0.085055 7
48 0.031563 5
46 0.025067 9
15 0.095445 2
57 0.011233 6
97 0.028239 2
8 0.060758 6
59 0.097330 13
34 0.052120 3
73 0.055127 11
53 0.004135 12
24 0.051183 5
56 0.027001 13

output:

3
16
4
2
11
5
19
7
9
10
8
17
1
6
14
12
18
13
20
15

result:

ok correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

20
971329 0.076234 0
996879 0.012978 0
994191 0.056803 0
978400 0.080792 1
907508 0.008858 4
992071 0.057419 2
901661 0.089621 6
912521 0.051943 5
979169 0.040201 5
904759 0.083405 7
928478 0.092658 7
980034 0.054747 3
906344 0.053231 10
907474 0.090196 8
927695 0.023153 4
995464 0.009387 2
984650 0...

output:

2
16
6
7
10
13
19
20
17
11
1
4
5
8
14
18
9
15
3
12

result:

ok correct

Test #6:

score: 0
Accepted
time: 2ms
memory: 3620kb

input:

20
54 0.952741 0
41 0.912397 0
11 0.963309 0
66 0.915806 3
47 0.919191 4
51 0.906473 5
24 0.989650 6
97 0.964070 7
56 0.997215 1
39 0.981950 2
50 0.994037 2
92 0.942000 7
97 0.900405 3
53 0.950071 6
16 0.980631 14
63 0.950876 10
49 0.995183 15
20 0.908520 5
71 0.949757 16
76 0.972330 9

output:

3
2
4
5
18
6
13
14
15
1
10
16
19
7
12
8
9
20
11
17

result:

ok correct

Test #7:

score: 0
Accepted
time: 2ms
memory: 3488kb

input:

20
933154 0.904059 0
929160 0.911627 0
999437 0.921760 0
991335 0.904136 1
903530 0.943148 4
904464 0.921035 2
944382 0.912394 6
990971 0.982189 7
941308 0.959290 4
993916 0.945081 7
924496 0.989350 1
938782 0.958578 4
964442 0.997198 11
964358 0.938647 10
911972 0.943888 5
975140 0.993873 4
995611 ...

output:

1
4
2
6
7
3
5
15
10
14
20
12
19
9
11
13
17
8
18
16

result:

ok correct

Test #8:

score: 0
Accepted
time: 2ms
memory: 3500kb

input:

1
10 0.5 0

output:

1

result:

ok correct

Test #9:

score: 0
Accepted
time: 2ms
memory: 3480kb

input:

2
100 0.8 0
200 0.7 0

output:

1
2

result:

ok correct

Test #10:

score: 0
Accepted
time: 2ms
memory: 3508kb

input:

2
10 0.5 0
5 0.4 1

output:

1
2

result:

ok correct

Test #11:

score: 0
Accepted
time: 2ms
memory: 3484kb

input:

2
1000 0.7 2
1 0.6 0

output:

2
1

result:

ok correct

Test #12:

score: 0
Accepted
time: 108ms
memory: 20028kb

input:

100000
938188 0.740681 0
575610 0.965656 1
937341 0.842524 2
817797 0.945396 3
602563 0.818956 4
893939 0.900203 5
952148 0.810399 6
538333 0.960769 7
550079 0.908188 8
676338 0.795726 9
546675 0.529045 10
542108 0.581119 11
963201 0.665127 12
564484 0.897025 13
504952 0.844118 14
673675 0.777947 15...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok correct

Test #13:

score: 0
Accepted
time: 83ms
memory: 14884kb

input:

100000
501234 0.500516 0
501214 0.503354 1
501013 0.504058 2
502546 0.502962 3
500273 0.505433 4
500197 0.505874 5
505941 0.500204 6
500455 0.506393 7
506433 0.500626 8
503652 0.503861 9
500935 0.507151 10
501370 0.506725 11
502595 0.506236 12
503444 0.505698 13
501723 0.508031 14
505738 0.504150 15...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok correct

Test #14:

score: 0
Accepted
time: 105ms
memory: 21432kb

input:

100000
768956 0.999996 0
686063 0.999982 1
817790 0.999964 2
897069 0.999958 3
940413 0.999956 4
879098 0.999957 5
687880 0.999964 6
663602 0.999959 7
816976 0.999944 8
572136 0.999958 9
653227 0.999946 10
972448 0.999914 11
836815 0.999920 12
617305 0.999941 13
934633 0.999903 14
757071 0.999917 15...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok correct

Test #15:

score: 0
Accepted
time: 106ms
memory: 15660kb

input:

100000
686602 0.755750 0
606835 0.951986 0
713656 0.504635 0
609527 0.663061 0
752558 0.613758 0
997011 0.880758 0
905135 0.574450 0
732880 0.774286 0
573515 0.609711 0
899010 0.630653 0
664787 0.949029 0
649162 0.965284 0
582075 0.957310 0
939848 0.848816 0
743139 0.738017 0
577134 0.723893 0
91476...

output:

253
67
161
137
179
1001
287
255
3403
97013
304
33
428
135
212
344
237
110
234
35
149
2447
65686
7360
281
267
357
235
11969
10350
55117
23101
44394
90
345
32287
94695
21214
188
5602
3
12430
219
17907
55
71206
152
87789
70
305
9
90656
238
210
5552
72776
205
236
6216
1136
648
1276
7802
92691
249
2763
5...

result:

ok correct

Test #16:

score: -100
Wrong Answer
time: 103ms
memory: 15600kb

input:

100000
866461 0.563475 0
566909 0.892585 1
794999 0.608805 1
572103 0.501998 1
889513 0.669248 4
712553 0.620050 3
721255 0.898776 3
731219 0.870250 5
958886 0.933100 5
946557 0.758386 1
829823 0.901169 6
513249 0.679404 6
707379 0.965023 2
686267 0.691424 13
790432 0.772695 3
630098 0.867609 11
975...

output:

1
4
255
1463
17335
2114
14926
25657
17157
19416
25749
33301
67686
2
43930
34070
382
2754
5745
5840
61325
61426
70
4349
739
5234
10413
2679
10128
14274
79762
30407
92693
98817
35
1243
11751
49724
94468
28424
41338
220
4584
702
10034
40074
1056
32441
28243
3
6
12
9550
123
1113
15255
26543
1657
3838
31...

result:

wrong answer your plan is not optimal