QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#351964#6561. Fail FastjanYWA 0ms3748kbC++203.6kb2024-03-12 17:54:412024-03-12 17:54:41

Judging History

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

  • [2024-03-12 17:54:41]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3748kb
  • [2024-03-12 17:54:41]
  • 提交

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