QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#569681#8790. First BillionHTensorTL 339ms18156kbC++232.6kb2024-09-17 04:37:002024-09-17 04:37:00

Judging History

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

  • [2024-09-17 04:37:00]
  • 评测
  • 测评结果:TL
  • 用时:339ms
  • 内存:18156kb
  • [2024-09-17 04:37:00]
  • 提交

answer

#include<iostream>
#include<vector>
#include<algorithm>
#include<random>
#include<array>
#define dd(x) cout << #x << "\n"
#define d(x) cout << #x  << ": " << x << "\n"
using namespace std;
#define int long long
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using a3 = array<int, 3>;
using ll = long long;
// const int inf = 0x3f3f3f3f3f3f3f3fLL;

const int mod = 4e4;

void solve() {
    int n; cin >> n;
    vector<int> ori(n + 1);
    vector<pair<int, int>> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> ori[i];
        a[i].first = ori[i] % mod;
        a[i].second = i;
    }

    if(n == 2) {
        cout << (ll) 1e9 << "\n";
        return ;
    }

    vector<int> ans;
    mt19937 rng(19260817);
    auto check = [&]() {
        shuffle(a.begin() + 1, a.end(), rng);
        vector dp(n + 1, vector<int> (mod + 1));
        vector fr(n + 1, vector<pair<int, int>>(mod + 1));
        ans.clear();
        int sum = 0;

        auto positive = [](int x) {
            int t = x % mod;
            if(t < 0) return t + mod;
            return t;
        };

        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < mod; j++) {
                int last = positive(j - a[i].first);
                if(dp[i - 1][j]) {
                    dp[i][j] = dp[i - 1][j];
                    fr[i][j] = fr[i - 1][j];
                } else if(dp[i - 1][last]) {
                    dp[i][j] = dp[i - 1][last];
                    fr[i][j] = {i - 1, last};
                }
            }

            if(dp[i][0]) {
                ans.push_back(a[i].second);
                auto [ii, ij] = fr[i][0];
                while(pair(ii, ij) != pair(0LL, 0LL)) {
                    ans.push_back(a[ii].second);
                    int nii = fr[ii][ij].first, njj = fr[ii][ij].second;
                    ii = nii, ij = njj;
                }
                break;
            }
            dp[i][a[i].first] = 1;
        }

        for(auto i : ans) {
            sum += ori[i];
        }

        if(sum != (long long)1e9) {
            return false;
        }
        return true;
    };

    while(!check()) {
        continue;
    }

    cout << ans.size() << " ";
    for(auto i : ans) {
        cout << i << " ";
    }
    cout << "\n";
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    while(T--) solve();
    return 0;
}

/*

10
386413329 88494216 245947398 316438989 192751270 204627269 65749456 3938400 150458676 345180997

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 14432kb

input:

10
386413329 88494216 245947398 316438989 192751270 204627269 65749456 3938400 150458676 345180997

output:

5 7 1 9 6 5 

result:

ok OK (n = 10)

Test #2:

score: 0
Accepted
time: 4ms
memory: 14508kb

input:

10
119486233 299942886 169540407 349937991 597883752 32230162 140514533 57341098 12602102 220520836

output:

5 5 6 8 9 2 

result:

ok OK (n = 10)

Test #3:

score: 0
Accepted
time: 275ms
memory: 18156kb

input:

14
384615281 84612238 83310504 54746763 142296081 56775470 128760350 343006424 177232390 214368720 67220468 21895072 16352717 224807522

output:

7 6 1 7 9 12 13 10 

result:

ok OK (n = 14)

Test #4:

score: 0
Accepted
time: 339ms
memory: 18088kb

input:

14
270208635 14270307 89661499 113578022 47687195 101043954 38775146 208193324 650676076 351701957 3427619 59535626 24230888 27009752

output:

7 4 1 2 10 12 6 3 

result:

ok OK (n = 14)

Test #5:

score: -100
Time Limit Exceeded

input:

20
61638928 106712373 5946815 178135484 4937573 111395400 15504655 67139983 101814514 312223647 130341028 43244171 37671364 54108486 337181317 37924824 153793862 70383750 102917244 66984582

output:


result: