QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#351964 | #6561. Fail Fast | janY | WA | 0ms | 3748kb | C++20 | 3.6kb | 2024-03-12 17:54:41 | 2024-03-12 17:54:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define ld long double
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define rev(x) reverse(x.begin(), x.end())
#define fi first
#define se second
#define pb push_back
#define PI 3.14159265359
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);}
#define sortpairbysec(x) sort(all(x), sortbysec)
bool sortcond(const pair<int,int> &a,const pair<int,int> &b){
if (a.fi != b.fi){
return a.fi < b.fi;
} else {
return a.se > b.se;
}
}
struct myComp {
constexpr bool operator()( pii const& a, pii const& b) const noexcept
{
if (a.first != b.first){
return a.first < b.first;
} else {
return a.second > b.second;
}
}
};
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rng(ll lim) {
uniform_int_distribution<ll> uid(0,lim-1);
return uid(rang);
}
const int mod = 998244353;
const int N = 3e5, M = N;
const ll inf = 1e18;
//=======================
//=======================
// & - bitwise AND; | - bitwise OR; ^ - bitwise XOR
// cout.precision(7);
// next_permutation(arr.begin(), arr.end());
// long long long long long long long long long long long long long long long long long long long long long long long long long long long
// priority_queue<int, vector<int>, greater<int>> a; (min heap)
// ll hash1 = hash<string>{}(to_string(1));
// always lower_bound
// __builtin_clz(n) count leading zeros
struct test {
ld chance_to_pass;
ld time_to_perform;
ld p_num; // priority number
vi liberates;
int needs;
void calc_pnum(){
p_num = time_to_perform/(1-chance_to_pass);
}
};
vl a;
ll n, m, k, q;
void solve(int tc) {
int i, j;
cin >> n;
vector<test> x(n);
fo(i, n){
ld tim, chance;
int dep;
cin >> tim >> chance >> dep;
dep--;
if (dep == -1) dep = n;
x[i].chance_to_pass = chance;
x[i].time_to_perform = tim;
x[i].needs = dep;
}
vi ans;
set<pair<ld, int>> p;
fo(i, n){
x[i].calc_pnum();
p.insert({x[i].p_num, i});
}
vi is_done(n+1);
is_done[n] = 1;
while (p.size()){
pair<ld, int> top = *p.begin();
p.erase(top);
int i = top.se;
int o = x[i].needs;
if (is_done[o] == 0) {
p.erase({x[o].p_num, o});
x[o].time_to_perform += x[i].time_to_perform;
x[o].chance_to_pass *= x[i].chance_to_pass;
x[o].liberates.pb(i);
x[o].calc_pnum();
p.insert({x[o].p_num, o});
continue;
}
ans.pb(i);
is_done[i] = 1;
for (auto &j : x[i].liberates){
p.insert({x[j].p_num, j});
}
}
for (auto &i : ans){
cout << i+1 << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
int t = 1;
// cin >> t;
int i;
fo(i, t) {
solve(i+1);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3740kb
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: 0ms
memory: 3748kb
input:
4 84 0.716 0 91 0.115 0 19 0.640 1 103 0.455 0
output:
2 4 1 3
result:
wrong answer your plan is not optimal