QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246800 | #7678. The Game | ucup-team052# | WA | 0ms | 3740kb | C++23 | 2.1kb | 2023-11-11 09:35:59 | 2023-11-11 09:36:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 300005
int a[N],b[N],n,m;
struct Node
{
int v,id;
bool operator < (const Node &x) const
{
if(v!=x.v) return v>x.v;
return id<x.id;
}
};
int attempt()
{
int w=0;
sort(a+1,a+n+1,greater<int>());
sort(b+1,b+m+1,greater<int>());
for(int i=1;i<=m;i++)
{
if(a[i]>b[i]) return -1;
w+=b[i]-a[i];
}
int go=n-m;
int res=go-w;
return res;
}
void work()
{
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) b[i]=read();
set<Node> s;
for(int i=1;i<=n;i++) s.insert((Node){a[i],i});
int pre=attempt();
sort(b+1,b+m+1);
// cout<<pre<<endl;
vector<int> ans;
for(int i=1;i<=pre;i++)
{
auto [w,id]=*s.rbegin();
// printf("* %d %d\n",w,id);
w++; ans.pb(w-1);
s.erase(--s.end());
s.insert((Node){w,id});
s.erase(--s.end());
}
for(int i=m;i>=1;i--)
{
if(s.begin()->v>b[i])
{
cout<<"-1\n";
return ;
}
while(s.begin()->v<b[i])
{
if(s.empty())
{
cout<<"-1\n";
return ;
}
auto [w,id]=*s.begin();
w++; ans.pb(w-1);
s.erase(s.begin());
s.insert((Node){w,id});
s.erase(--s.end());
}
s.erase(s.begin());
}
while((int)ans.size()<n-m)
{
auto [w,id]=*s.rbegin();
w++; ans.pb(w-1);
if(w>b[m])
{
cout<<"-1\n";
return ;
}
s.erase(--s.end());
s.insert((Node){w,id});
s.erase(--s.end());
}
cout<<ans.size()<<endl;
print(ans);
}
signed main()
{
int T=read(); while(T--) work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
6 5 3 1 2 2 3 3 2 3 4 4 2 1 2 2 4 2 4 5 2 2 3 3 4 4 5 5 6 1 1 1 1 1 1 1 4 4 2 1 1 1 2 2 2 4 1 1 1 1 1 2
output:
2 1 3 -1 3 2 4 4 5 1 1 2 3 2 2 1 1 -1
result:
ok ok (6 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
7056 4 3 1 1 1 1 1 1 1 4 3 1 1 1 1 1 1 2 4 3 1 1 1 1 1 1 3 4 3 1 1 1 1 1 1 4 4 3 1 1 1 1 1 1 5 4 3 1 1 1 1 1 1 6 4 3 1 1 1 1 1 2 2 4 3 1 1 1 1 1 2 3 4 3 1 1 1 1 1 2 4 4 3 1 1 1 1 1 2 5 4 3 1 1 1 1 1 2 6 4 3 1 1 1 1 1 3 3 4 3 1 1 1 1 1 3 4 4 3 1 1 1 1 1 3 5 4 3 1 1 1 1 1 3 6 4 3 1 1 1 1 1 4 4 4 3 1 1...
output:
-1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 2 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok ok (7056 test cases)
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3708kb
input:
5880 4 2 1 1 1 1 1 1 4 2 1 1 1 1 1 2 4 2 1 1 1 1 1 3 4 2 1 1 1 1 1 4 4 2 1 1 1 1 1 5 4 2 1 1 1 1 1 6 4 2 1 1 1 1 1 7 4 2 1 1 1 1 2 2 4 2 1 1 1 1 2 3 4 2 1 1 1 1 2 4 4 2 1 1 1 1 2 5 4 2 1 1 1 1 2 6 4 2 1 1 1 1 2 7 4 2 1 1 1 1 3 3 4 2 1 1 1 1 3 4 4 2 1 1 1 1 3 5 4 2 1 1 1 1 3 6 4 2 1 1 1 1 3 7 4 2 1 1...
output:
-1 2 1 1 2 1 2 -1 -1 -1 -1 2 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 2 3 -1 -1 -1 2 1 1 2 2 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 3 4 -1 -1 -1 2 1 1 2 3 1 -1 -1 -1 2 1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 4...
result:
wrong answer Wrong answer, the final sequence does not equal to B (test case 2)