QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#569681 | #8790. First Billion | HTensor | TL | 339ms | 18156kb | C++23 | 2.6kb | 2024-09-17 04:37:00 | 2024-09-17 04:37:00 |
Judging History
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