QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#576780 | #8790. First Billion | Legend_dy# | WA | 6ms | 3600kb | C++20 | 935b | 2024-09-19 22:20:51 | 2024-09-19 22:20:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int M = 1e9;
int average;
int n, a[101], vis[101];
unordered_map<int, bool> dp[101];
vector<int> stk;
void dfs(int u, int sum) {
if (dp[u].count(sum)) return;
if (sum == M) {
for (int x : stk) cout << x + 1 << ' ';
exit(0);
}
vector<pair<int, int>> b;
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
b.emplace_back(abs(a[i] - (average * u / n)), i);
}
sort(b.begin(), b.end());
for (auto [x, i] : b) {
vis[i] = 1;
stk.push_back(i);
dp[u][sum + a[i]] = 1;
dfs(u + 1, sum + a[i]);
stk.pop_back();
vis[i] = 0;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
average = M / n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
dfs(1, 0);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 3600kb
input:
10 386413329 88494216 245947398 316438989 192751270 204627269 65749456 3938400 150458676 345180997
output:
8 2 3 4 10
result:
wrong output format Unexpected end of file - int32 expected