QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#338583 | #6561. Fail Fast | lolicon | WA | 1ms | 5796kb | C++20 | 1.3kb | 2024-02-26 01:24:08 | 2024-02-26 01:24:09 |
Judging History
answer
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int maxn = 1e5 + 5;
int c[maxn], d[maxn], p[maxn];
vector<int> G[maxn];
int n;
int get(string &s) {
while(s.length() < 8)
s.push_back('0');
int ret = 0;
for(char c : s)
ret = ret * 10 + (c - '0');
return ret;
}
struct item {
int c, p, id;
item(int _a, int _b, int _c) :
c(_a), p(_b), id(_c) {}
};
struct cmp {
bool operator()(const item &a, const item &b) {
return a.c * b.p < b.c * b.c;
}
};
void solve() {
cin >> n;
for(int i = 1; i <= n; ++i) {
string s; int u;
cin >> c[i] >> s >> u;
p[i] = get(s);
if(u) {
G[u].emplace_back(i); d[i]++;
}
}
priority_queue<item, vector<item>, cmp> pq;
for(int i = 1; i <= n; ++i) {
if(!d[i]) pq.emplace(c[i], p[i], i);
}
vector<int> ans;
while(pq.size()) {
item x = pq.top(); pq.pop();
ans.emplace_back(x.id);
for(int y : G[x.id]) {
if(!--d[y]) pq.emplace(c[y], p[y], y);
}
}
for(int x : ans) cout << x << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5796kb
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: -100
Wrong Answer
time: 1ms
memory: 5680kb
input:
4 84 0.716 0 91 0.115 0 19 0.640 1 103 0.455 0
output:
4 2 1 3
result:
wrong answer your plan is not optimal