QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#754991 | #9574. Strips | Alucard | WA | 101ms | 3884kb | C++14 | 4.0kb | 2024-11-16 16:12:12 | 2024-11-16 16:12:12 |
Judging History
answer
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define i128 _int128
#define fi first
#define se second
#define pb push_back
#define endl '\n'
//#define int long long
const ll INF=0x3f3f3f3f;
const int N=1e9,M=1e9+9;
const ll mod=998244353;
int read(){
int s=0,w=1;
char c=getchar();
while(!isdigit(c)) (c=='-')?w=-1:w=1,c=getchar();
while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
return s*w;
}
int qpow(int a,int b){
a%=mod;
int res=1;
while(b){
if(b&1){res=(res*a)%mod;}
a=(a*a)%mod;
b>>=1;
}
return res%mod;
}
// int inverse(int a){
// a%=mod;
// return qpow(fac[a%mod],mod-2)%mod;
// }
// int C(int n,int r){
// n%=mod,r%=mod;
// if(r>n)return 0;
// return ((fac[n%mod]*inverse(r))%mod*inverse(n-r))%mod;
// }
// int Lucas(int n,int r){
// if(r==0)return 1;
// return C(n%mod,r%mod)%mod*Lucas(n/mod,r/mod)%mod;
// }
int n,m,k,w;
void solve(){
deque<int> ans;//答案下标存放
priority_queue<int,vector<int>,greater<int> > id,id1,r,b;//红黑格下标存放
map<int,int> s,vis;//红黑格空间、标记存放,黑不包含自己,红包含
// int sr=0,sb=0;//红黑格空间计算媒介
int ir=0,ib=0;//上个红、黑格下标
cin>>n>>m>>k>>w;
for(int i=1;i<=n;++i){
int x;cin>>x;r.push(x);
vis[x]=1;
id.push(x);id1.push(x);
}
for(int i=1;i<=m;++i){
int x;cin>>x;b.push(x);
vis[x]=2;
id.push(x);id1.push(x);
}
b.push(w+1),vis[w+1]=2;
id.push(w+1),id1.push(w+1);//最右侧
while(!id.empty()){
int temp=id.top();id.pop();
if(vis[temp]==1){s[temp]=temp-max(ir,ib),ir=temp;}
if(vis[temp]==2){s[temp]=temp-ib-1,ir=0,ib=temp;}
//cout<<temp<<':'<<s[temp]<<" "<<id.size()<<endl;//test
}
int cnt=0;
int res=0;//上条strip可向右滑动的最大空间
while(!id1.empty()){
int i=id1.top();id1.pop();
if(vis[i]==1){//红格
if(s[i]<=res){//前一条可向右滑动覆盖当前红格
//cout<<i<<' '<<"case11"<<endl;
//cout<<s[i]<<endl;
int temp=ans.back();ans.pop_back();
temp+=s[i];res-=s[i];
ans.push_back(temp);
r.pop();//弹出已用过的格
if(b.top()>r.top()){
//cout<<r.top()<<' '<<s[r.top()]<<endl;
s[r.top()]-=(s[i]-1);//更新下一红格空间
//cout<<s[r.top()]<<endl;
}
}
else if(s[i]>=k){//红格前面空间足够放整条strip
//cout<<"case12"<<endl;
ans.push_back(i-k+1);cnt++;
r.pop();
s[b.top()]-=k;
}
else{
if(s[b.top()]>=k){//后面空间足够放剩余strip
//cout<<i<<' '<<"case131"<<endl;
ans.push_back(i-s[i]+1);cnt++;
res=s[i]-1;
r.pop();
s[b.top()]-=k;
if(b.top()>r.top())s[r.top()]-=k-s[i];
}
else{//无法放strip
//cout<<"case132"<<endl;
cout<<-1<<endl;return;
}
}
}
else if(vis[i]==2){//黑格
//cout<<"case12"<<endl;
res=0;
b.pop();//弹出已用过的格
}
}
cout<<cnt<<endl;
for(auto x:ans)cout<<x<<' ';
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int _=1;
// fac[0]=1;
// for(int i=1;i<=N-9;++i)fac[i]=(fac[i-1]*i)%mod;
cin>>_;
while(_--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3508kb
input:
4 5 2 3 16 7 11 2 9 14 13 5 3 2 4 11 6 10 2 1 11 2 1 2 6 1 5 3 2 1 2 6 1 5 2
output:
4 1 7 10 14 -1 2 1 4 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 101ms
memory: 3884kb
input:
11000 3 8 2 53 32 3 33 35 19 38 20 1 30 10 6 7 10 1 42 3 14 4 36 28 40 22 17 20 12 41 27 7 1 19 13 9 6 6 13 78 55 76 53 32 54 58 62 45 21 4 7 61 8 7 3 68 9 26 54 31 22 3 38 65 34 16 58 47 52 29 53 5 8 4 33 33 5 30 6 15 27 12 9 28 19 2 13 10 6 1 2 48 8 12 48 1 41 31 40 7 6 7 61 20 19 30 52 49 17 40 3...
output:
3 2 31 33 7 3 4 14 22 28 36 40 3 22 46 64 8 1 7 20 24 30 36 54 63 3 3 14 30 6 1 7 11 30 41 47 5 11 14 27 34 46 3 42 57 68 3 18 20 27 1 22 1 62 7 24 32 34 42 47 59 61 3 3 30 32 3 11 19 29 3 2 15 33 3 25 30 42 4 2 16 18 59 4 -3 6 19 32 2 53 65 4 49 58 64 66 4 44 60 70 78 2 69 78 4 1 11 15 21 6 3 7 17 ...
result:
wrong answer Participant's answer is 3. But jury has a better answer 2. (test case 1)