QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#395716 | #7678. The Game | zzuqy# | TL | 1ms | 7952kb | C++14 | 4.4kb | 2024-04-21 17:40:36 | 2024-04-21 17:40:36 |
Judging History
answer
#include<bits/stdc++.h>
#include<iomanip>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<deque>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<stack>
#include<algorithm>
#include<vector>
#include<cctype>
#include<utility>
#include<set>
#include<bitset>
#include<map>
#define ll long long
#define db double
#define INF 1000000000
#define inf 100000000000000000ll
#define ldb long double
#define pb push_back
#define put_(x) printf("%d ",x)
#define putl_(x) printf("%lld ",x)
#define get(x) x=read()
#define putl(x) printf("%lld\n",x)
#define rep(p,n,i) for(int i=p;i<=n;i+=1)
#define fep(n,p,i) for(int i=n;i>=p;--i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define pii pair<int,int>
#define mk make_pair
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define uint unsigned long long
#define ui unsigned
#define sq sqrt
#define x(w) t[w].x
#define r(w) t[w].r
#define l(w) t[w].l
#define yy p<<1|1
#define zz p<<1
#define sum(w) t[w].sum
#define mod 1000000007
#define sc(A) scanf("%d",&A)
#define scl(A) scanf("%lld",&A)
#define scs(A) scanf("%s",A)
#define put(A) printf("%d\n",A)
#define min(x,y) (x>=y?y:x)
#define max(x,y) (x>=y?x:y)
#define sub(x,y) (x-y<0?x-y+mod:x-y)
using namespace std;
const int MAXN=300010<<1;
int T;
int m,n;
int a[MAXN],b[MAXN];
int q[MAXN],L;
int cmp(int x,int y){return x>y;}
priority_queue<int, vector<int>, greater<int> > s;
void SC()
{
while(s.size()>m)s.pop();
rep(1,m,i)
{
a[m-i+1]=s.top();
s.pop();
}
rep(1,m,i)
{
while(a[i]<b[i])
q[++L]=a[i],++a[i];
}
}
int main()
{
//freopen("1.in","r",stdin);
//srand(time(0));
sc(T);
//T=rand()%100;
while(T--)
{
// n=rand()%1000+1;
// m=rand()%1000+1;
// rep(1,n,i)a[i]=rand()%1000+1;
// rep(1,m,i)b[i]=rand()%1000+1;
sc(n);sc(m);
rep(1,n,i)sc(a[i]);
rep(1,m,i)sc(b[i]);
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+m,cmp);
int res=n-m;ll sum=0;
L=0;int flag=0;
while(s.size())s.pop();
rep(1,m,i)
{
if(a[i]>b[i])flag=1;
else sum+=b[i]-a[i];
}
if(flag)
{
put(-1);
continue;
}
if(sum>res)
{
put(-1);
continue;
}
if(sum==0&&res==0)
{
put(0);
continue;
}
rep(1,n,i)s.push(a[i]);
int ww=0;
while(1)
{
auto it=s.top();
int x=it;
if(x==b[m]&&ww)
{
flag=1;
break;
}
ww=1;
int cnt=0;
while(x==it)
{
++cnt;
s.pop();
if(s.size()==0)break;
else it=s.top();
}
//cout<<s.size()<<endl;
int CC=max(0,m-(int)s.size());
if(CC==0)
{
while(1)
{
if(sum==s.size()-m+cnt)
{
SC();
goto mark;
}
if(!cnt)break;
else
{
--cnt;q[++L]=x;
if(cnt)s.push(x+1),--cnt;
}
}
}
else
{
while(1)
{
if(sum==s.size()-m+cnt)
{
while(cnt)s.push(x),--cnt;
SC();
goto mark;
}
if(!cnt)break;
else
{
--cnt;
q[++L]=x;
if(CC)--sum,--CC,s.push(x+1),--cnt;
else
{
if(cnt)s.push(x+1),--cnt;
}
}
}
}
}
if(flag)
{
put(-1);
continue;
}
mark:
put(L);
rep(1,L,i)put_(q[i]);
puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7952kb
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 1 2 3 2 1 1 -1
result:
ok ok (6 test cases)
Test #2:
score: -100
Time Limit Exceeded
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...