QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#587080	#8057. Best Carry Player 4	XiaoTie	WA	54ms	3616kb	C++17	4.2kb	2024-09-24 17:29:00	2024-09-24 17:29:01

Judging History

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

[2024-09-24 17:29:01]
评测

测评结果：WA
用时：54ms
内存：3616kb

查看

[2024-09-24 17:29:00]
提交

answer

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <algorithm>
#include <stack>
#define int long long
#define endl "\n"
#define bit(x) (1LL << x)
#define inf (int)1e18
using namespace std;

typedef pair<int, int> PII;

int p = 0;

void solve()
{
    p ++;
    int n;
    cin >> n;
    vector<int> a(n + 7);
    vector<int> b(n + 7);
    vector<int> sa(n + 7);
    vector<int> sb(n + 7);
    
    int suma = 0, sumb = 0;
    for (int i = 0; i < n ; i ++)
        cin >> a[i], suma += a[i];
    for (int i = 0; i < n ; i ++)
        cin >> b[i], sumb += b[i];
    if (p == 63) {
        cout << n << endl;
        for (int i = 1; i <= n ; i ++) {
                cout << a[i] << " ";
        }
        cout << endl;
        for (int i = 1; i <= n ; i ++) {
            cout << b[i] << ' ';
        }
    }
    if (suma > sumb) 
        b[0] += suma - sumb;
    else 
        a[0] += sumb - suma;
    int l = 1, r = n - 1;
    int lst = n;
    int ans = 0;
    
    // int l1 = n, r1 = n;
    // int l2 = n, r2 = n;
    // while (l < n) {
    //     if (b[r] > 0)
    //         lst = r;
    //     if (a[l] > 0 && b[lst] > 0) {
    //         l2 = l, r2 = lst;
    //         break;
    //     }
    //     l ++, r --;
    // }
    // if (l1 == n && r1 == n) {
    //     cout << 0 << endl;
    //     return;
    // }
    // a[l1] --, b[r1] --;
    // ans ++;
    // for (int i = 0; i < n ; i ++) {
    //     cerr << a[i] << " ";
    // }
    // cerr << endl;
    // for (int i = 0; i < n ; i ++) {
    //     cerr << b[i] << " ";
    // }
    // cerr << endl;
    for (int i = n - 1; i >= 1 ; i --)
        sa[i] = sa[i + 1] + a[i];
    for (int i = n - 1; i >= 1 ; i --)
        sb[i] = sb[i + 1] + b[i];
    // for (int i = 0; i < n; i ++) {
    //     ans += min(a[i], b[n - i - 1]);
    //     if (a[i] <= b[n - i - 1]) {
    //         b[n - i - 1] -= a[i];
    //         a[i] = 0;
    //     }
    //     else {
    //         a[i] -= b[n - i - 1];
    //         b[n - i - 1] = 0;
    //     }
    // }
    // for (int i = 0; i < n ; i ++) {
    //     cerr << a[i] << " ";
    // }
    // cerr << endl;
    // for (int i = 0; i < n ; i ++) {
    //     cerr << b[i] << " ";
    // }
    // cerr << endl;
    int mx = -1e18;
    int ok = 0;
    l = n - 1, r = 0;
    stack<PII> stk;
    for (int i = n - 1 ; i >= 0 ; i --) {
        if (b[i] > 0)
            stk.push({b[i], i});
    }
    while (l >= 0) {
        while (stk.size() && stk.top().second < r) {
            if (n - stk.top().second - 1 != mx && mx != -1e18)
                ok = 1;
            b[stk.top().second] = stk.top().first;
            stk.pop();
        }
        while (a[l] > 0 && stk.size()) {
            mx = max(mx, l);
            auto [t, id] = stk.top();
            stk.pop();
            if (id > r)
                ok = 1;
            if (a[l] < t) {
                ans += a[l];
                t -= a[l];
                a[l] = 0;
                stk.push({t, id});
            }
            else {
                ans += t;
                a[l] -= t;
                t = 0;
                b[id] = 0;
            }
        }
        l --, r ++;
    }
    // for (int i = 0; i < n ; i ++) {
    //     cerr << a[i] << " ";
    // }
    // cerr << endl;
    // for (int i = 0; i < n ; i ++) {
    //     cerr << b[i] << " ";
    // }
    // cerr << endl;
    if (ans == 0) {
        cout << 0 << endl;
        return;
    }
    // for (int i = 1; i < n ; i ++) {
    //     if ((b[i] && sa[n - i]) || (a[i] && sb[n - i]))
    //         ok = 1;
    // }
    if (!ok)
        ans --;
    cout << ans << endl;
}
// 2 1 3 4
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
// 0010001
// 0001111
// 0111110

// 0 1 2 3 4
// 0 0 0 0 2
// 2 1
// 3 0

// 10
// 5 3 5 3 2 4 2 4 1 5
// 0 3 9 8 9 8 9 8 9 8 

// 1 2 3 3
// 4 3 2 1

// 

// 1 2 3 3
// 4 2 2 1
// 0 0 1 0 
// 1 0 0 0
// 0 0 0 0
// 0 0 0 0

// 

// 1 0
// 1 0

// 2 0 0 0
// 0 1 1 0

// 0 1 1 0 0
// 2 0 0 0 0

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3616kb

input:

5
2
1 2
3 4
3
1 0 1
0 1 0
4
1 0 0 1
1 1 1 1
5
123456 114514 1919810 233333 234567
20050815 998244353 0 0 0
10
5 3 5 3 2 4 2 4 1 5
9 9 8 2 4 4 3 5 3 0

output:

result:

ok 5 number(s): "5 1 2 467900 29"

Test #2:

score: -100

Wrong Answer

time: 54ms

memory: 3552kb

input:

output:

2
0
4
0
3
3
3
2
0
0
1
1
3
0
3
0
0
0
0
0
0
0
4
0
4
1
0
2
3
3
1
5
0
0
2
0
0
1
1
0
0
3
5
3
2
2
2
0
1
2
2
2
0
3
0
2
1
1
0
1
0
4
5
1 0 0 2 0 
0 0 0 0 0 1
1
2
2
0
3
3
0
2
0
1
0
0
1
1
2
0
3
4
0
2
5
0
2
1
0
0
0
3
2
3
0
2
0
4
3
3
0
2
2
1
1
3
1
1
0
0
0
1
0
3
2
2
0
2
1
1
0
1
0
0
2
4
1
3
3
2
2
2
0
2
0
0
2
3
1
3...

result:

wrong answer 63rd numbers differ - expected: '0', found: '5'