QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515219#9178. All-You-Can-Eatucup-team045WA 1ms3496kbC++207.5kb2024-08-11 16:08:582024-08-11 16:08:58

Judging History

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

  • [2024-08-11 16:08:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3496kb
  • [2024-08-11 16:08:58]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<cassert>
using namespace std;
using LL = long long;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        int sum = 0;
        set<pair<int, int> > s;
        for(int i = 1; i <= n; i++){
            int x;
            cin >> x;
            if (sum >= 600){
                cout << 0 << endl;
                cout << "IGNORE" << endl;
                continue;
            }
            if (sum + x <= 1000){
                s.insert({x, i});
                sum += x;
                cout << 0 << endl;
                cout << "TAKE" << endl;
                continue;
            }
            // {
            //     auto it = s.lower_bound({600 - x, 0});
            //     if (it != s.end() and it->first + x <= 1000){
            //         s.erase(it);
            //         cout << s.size() << endl;
            //         for(auto [x, y] : s){
            //             cout << y << ' ';
            //         }
            //         cout << endl;
            //         sum = 600;
            //         cout << "TAKE" << endl;
            //         continue;
            //     }
            // }

            vector<pair<int, int> > v(s.begin(), s.end());
            int ss = 0;
            bool ok = false;
            for(int i = 0; i < v.size(); i++){
                ss += v[i].first;
                if (ss + x >= 600 and ss + x <= 1000){
                    cout << v.size() - i - 1 << endl;
                    for(int j = i + 1; j < v.size(); j++){
                        cout << v[j].second << ' ';
                    }
                    cout << endl;
                    cout << "TAKE" << endl;
                    ok = true;
                    break;
                }
            }
            if (ok) continue;
            ss = 0;
            for(int i = int(v.size()) - 1; i >= 0; i--){
                ss += v[i].first;
                if (ss + x >= 600 and ss + x <= 1000){
                    cout << i << endl;
                    for(int j = 0; j < i; j++){
                        cout << v[j].second << ' ';
                    }
                    cout << endl;
                    cout << "TAKE" << endl;
                    ok = true;
                    break;
                }
            }
            if (ok) continue;

            if (x >= 600){
                cout << s.size() << '\n';
                for(auto [x, y] : s){
                    cout << y << ' ';
                }
                cout << endl;
                cout << "TAKE" << endl;
                s.clear();
                s.insert({x, i});
                sum = x;
            }
            else if (x > 500){
                
                

                if ((sum - prev(s.end())->first + x >= 600 and sum - prev(s.end())->first + x <= 1000)){
                    sum = sum - prev(s.end())->first + x;
                    cout << 1 << endl;
                    cout << prev(s.end())->second << endl;
                    s.erase(prev(s.end()));
                    s.insert({x, i});
                    cout << "TAKE" << endl;
                }
                else if (prev(s.end())->first + x >= 600 and prev(s.end())->first + x <= 1000){
                    cout << s.size() - 1 << endl;
                    while(s.size() > 1){
                        cout << s.begin()->second << ' ';
                        s.erase(s.begin());
                    }
                    cout << endl;
                    cout << "TAKE" << endl;
                    sum = s.begin()->first + x;
                    s.insert({x, i});
                }
                else if (x < prev(s.end())->first){
                    sum = sum - prev(s.end())->first + x;
                    cout << 1 << endl;
                    cout << prev(s.end())->second << endl;
                    s.erase(prev(s.end()));
                    s.insert({x, i});
                    cout << "TAKE" << endl;
                }
                else{
                    cout << 0 << endl;
                    cout << "IGNORE" << endl;
                }
            }
            else{
                if ((sum - prev(s.end())->first + x >= 600 and sum - prev(s.end())->first + x <= 1000)){
                    sum = sum - prev(s.end())->first + x;
                    cout << 1 << endl;
                    cout << prev(s.end())->second << endl;
                    s.erase(prev(s.end()));
                    s.insert({x, i});
                    cout << "TAKE" << endl;
                }
                else if (prev(s.end())->first + x >= 600 and prev(s.end())->first + x <= 1000){
                    cout << s.size() - 1 << endl;
                    while(s.size() > 1){
                        cout << s.begin()->second << ' ';
                        s.erase(s.begin());
                    }
                    cout << endl;
                    cout << "TAKE" << endl;
                    sum = s.begin()->first + x;
                    s.insert({x, i});
                }
                else if (prev(s.end())->first > 500){
                    sum = sum - prev(s.end())->first + x;
                    cout << 1 << endl;
                    cout << prev(s.end())->second << '\n';
                    s.erase(prev(s.end()));
                    s.insert({x, i});
                    cout << "TAKE" << endl;
                    // assert(sum <= 1000);
                }
                else{
                    vector<pair<int, int> > p(s.begin(), s.end());
                    const int m = p.size();
                    vector<vector<int> > dp(m + 1, vector<int>(1001));
                    vector<vector<int> > pre(m + 1, vector<int>(1001));
                    dp[0][x] = 1;
                    
                    for(int i = 0; i < m; i++){
                        for(int j = 0; j <= 1000; j++){
                            if (dp[i][j]){
                                dp[i + 1][j] = 1;
                                pre[i + 1][j] = 0;
                                if (j + p[i].first <= 1000){
                                    dp[i + 1][j + p[i].first] = 1;
                                    pre[i + 1][j + p[i].first] = 1;
                                }
                            }
                        }
                    }
                    int t = 600;
                    while(t <= 1000 and !dp[m][t]) t++;
                    assert(t <= 1000);
                    vector<pair<int, int> > del;
                    s.clear();
                    int ss = 0;
                    int bk = t;
                    for(int i = m; i >= 1; i--){
                        if (pre[i][t]){
                            t -= p[i - 1].first;
                            ss += p[i - 1].first;
                        }
                        else{
                            del.push_back(p[i - 1]);
                        }
                    }
                    assert(ss + x == bk);
                    cout << del.size() << endl;
                    for(auto [x, y] : del){
                        cout << y << ' ';
                    }
                    cout << endl;
                    sum = 600;
                    cout << "TAKE" << endl;
                }
            }
        }
    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3496kb

input:

1
5
10
13
450
585
465

output:

0
TAKE
0
TAKE
0
TAKE
1
3 
TAKE
0
TAKE

result:

wrong output format Unexpected end of file - int32 expected (test case 1)