QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#509570 | #9178. All-You-Can-Eat | PhantomThreshold# | AC ✓ | 0ms | 3832kb | C++20 | 3.0kb | 2024-08-08 16:08:28 | 2024-08-08 16:08:30 |
Judging History
answer
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
//#define int long long
using namespace std;
//using namespace __gnu_pbds;
//#define double long double
int a[110000],b[110000];
int f[110][1010];
int dp(int n)
{
f[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=1000;j++) if(f[i-1][j])
{
f[i][j]=1;
if(j+a[i]<=1000) f[i][j+a[i]]=1;
}
}
int mx=0;
for(int j=0;j<=1000;j++) if(f[n][j]) mx=j;
return (int)(0.6*mx);
}
int cksum;
signed main()
{
/////////////////////////////////////////////////
//freopen("tmp.in","r",stdin);
ios_base::sync_with_stdio(false);
//cin.tie(0);
mt19937 mt((unsigned long long)(new char));
int Tcase; cin>>Tcase;
while(Tcase--)
{
int n; n=10; cksum=0;
cin>>n;
set< pair<int,int> >S;
int sum=0, X=0, Xi;
for(int i=1;i<=n;i++)
{
int c=mt()%1000+1;
cin>>c;
a[i]=c; b[i]=0;
if(sum>600)
{
cout<<"0"<<endl<<"IGNORE"<<endl;
continue;
}
if(c>600)
{
vector<int>V;
if(X)
{
V.push_back(Xi);
sum-=X;
}
while(S.size()>0)
{
auto it=S.begin();
V.push_back(it->second);
sum-=it->first;
S.erase(it);
}
cout<<V.size();
for(auto j:V)
{
cout<<' '<<j;
assert(b[j]==1);
b[j]=0;
cksum-=a[j];
}
cout<<endl;
sum+=c;
cout<<"TAKE"<<endl;
b[i]=1; cksum+=a[i];
assert(cksum<=1000);
}
else if( c<=400 )
{
cout<<"0"<<endl<<"TAKE"<<endl;
b[i]=1; cksum+=a[i];
assert(cksum<=1000);
sum+=c;
S.emplace( c,i );
}
else
{
if( X==0 )
{
vector<int>V;
while(sum+c>1000)
{
auto it=S.end(); it--;
V.push_back(it->second);
sum-=it->first;
S.erase(it);
}
cout<<V.size();
for(auto j:V)
{
cout<<' '<<j;
assert(b[j]==1);
b[j]=0;
cksum-=a[j];
}
cout<<endl;
sum+=c;
cout<<"TAKE"<<endl;
b[i]=1; cksum+=a[i];
assert(cksum<=1000);
X=c; Xi=i;
}
else
{
if( X+c <= 1000 )
{
vector<int>V;
while(S.size()>0)
{
auto it=S.begin();
V.push_back(it->second);
sum-=it->first;
S.erase(it);
}
cout<<V.size();
for(auto j:V)
{
cout<<' '<<j;
assert(b[j]==1);
b[j]=0;
cksum-=a[j];
}
cout<<endl;
sum+=c;
cout<<"TAKE"<<endl;
b[i]=1; cksum+=a[i];
assert(cksum<=1000);
}
else if(X<=c)
{
cout<<"0"<<endl<<"IGNORE"<<endl;
}
else
{
cout<<"1 "<<Xi<<endl;
assert(b[Xi]==1);
b[Xi]=0;
cksum-=a[Xi];
sum+= c-X;
X=c; Xi=i;
cout<<"TAKE"<<endl;
b[i]=1; cksum+=a[i];
assert(cksum<=1000);
}
}
}
}
// assert(cksum>dp(n));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3832kb
input:
1 5 oblivious 10 13 450 585 465
output:
0 TAKE 0 TAKE 0 TAKE 0 IGNORE 0 IGNORE
result:
wrong answer Integer parameter [name=n] equals to 0, violates the range [1, 10000] (test case 1)