QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515219 | #9178. All-You-Can-Eat | ucup-team045 | WA | 1ms | 3496kb | C++20 | 7.5kb | 2024-08-11 16:08:58 | 2024-08-11 16:08:58 |
Judging History
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)