QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#696823	#8237. Sugar Sweet II	Catreap	WA	132ms	19316kb	C++23	2.7kb	2024-11-01 02:37:08	2024-11-01 02:37:09

Judging History

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

[2024-11-04 16:59:03]
hack成功，自动添加数据
(/hack/1109)

[2024-11-01 02:37:09]
评测

测评结果：WA
用时：132ms
内存：19316kb

查看

[2024-11-01 02:37:08]
提交

answer

#include <bits/stdc++.h>

using ll = long long;

const ll N = 2e6 + 5;

const ll M = 1e9 + 7;

ll qpow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) {
            ret = (ret * a) % M;
        }
        a = (a * a) % M;
        b >>= 1;
    }
    return ret;
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ll T;
    std::cin >> T;
    std::vector<ll> fac(N + 1);
    fac[0] = 1;
    for (ll i = 1; i <= N; i++) {
        fac[i] = fac[i - 1] * i % M;
    }
    while (T--) {
        ll n;
        std::cin >> n;
        std::vector<ll> a(n + 1);
        std::vector<ll> b(n + 1);
        std::vector<ll> w(n + 1);
        std::vector<ll> vis(n + 1);
        std::vector<ll> dp(n + 1), dep(n + 1);
        std::vector<ll> stk(n + 1);
        ll top = 0;
        for (ll i = 1; i <= n; i++) {
            std::cin >> a[i];
        }
        for (ll i = 1; i <= n; i++) {
            std::cin >> b[i];
        }
        for (ll i = 1; i <= n; i++) {
            std::cin >> w[i];
        }
        auto work = [&](auto&& self, ll i) -> void {
            if (vis[i] == 2) {
                return;
            }
            if (vis[i] == 1) {
                while (top && stk[top - 1] != i) {
                    top--;
                    vis[stk[top]] = 2;
                    dp[stk[top]] = a[stk[top]];
                    dep[stk[top]] = 1;
                }
                top--;
                vis[stk[top]] = 2;
                dp[stk[top]] = a[stk[top]];
                dep[stk[top]] = 1;
                return;
            }
            vis[i] = 1;
            stk[top++] = i;
            if (a[i] < a[b[i]]) {
                dp[i] = (a[i] + w[i]) % M;
                dep[i] = 1;
            } else if (a[i] >= a[b[i]] + w[b[i]]) {
                dp[i] = a[i] % M;
                dep[i] = 1;
            } else {
                self(self, b[i]);
                if (vis[i] == 2) {
                    return;
                }
                dep[i] = dep[b[i]] + 1;
                dp[i] = (a[i] + qpow(fac[dep[i]], M - 2) * w[i] % M) % M;
            }
            vis[i] = 2;
            top--;
        };
        for (ll i = 1; i <= n; i++) {
            if (vis[i]) {
                continue;
            }
            if (b[i] == i) {
                vis[i] = 2;
                dp[i] = a[i] % M;
                dep[i] = 1;
                continue;
            }
            work(work, i);
        }
        for (ll i = 1; i <= n; i++) {
            printf(" %lld" + !(i - 1), dp[i]);
        }
        printf("\n");
    }
    return 0;
}
/*
1
3
5 4 3
2 3 1
1 2 3
*/

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 12ms

memory: 18700kb

input:

output:

500000007 5 5 6
5 10 9
166666673 5 6
500000006 4 3 4 5

result:

ok 15 numbers

Test #2:

score: -100

Wrong Answer

time: 132ms

memory: 19316kb

input:

50000
5
508432375 168140163 892620793 578579275 251380640
3 4 4 1 3
346232959 736203130 186940774 655629320 607743104
1
863886789
1
364158084
18
864679185 463975750 558804051 604216585 694033700 499417132 375390750 337590759 467353355 111206671 983760005 984444619 322277587 138763925 205122047 97736...

output:

854665334 904343293 590444253 906393935 859123744
863886789
871186919 814243920 968784984 206455474 17527050 449261413 196759729 901433117 519383814 907574792 983760005 984444619 489899014 435736558 113628626 977360756 482247153 963066959
902284038 240323331 132646723 421298438 601054667 99438820 94...

result:

wrong answer 25th numbers differ - expected: '665922935', found: '902284038'