QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#755018 | #9574. Strips | Alucard | WA | 109ms | 3656kb | C++14 | 4.0kb | 2024-11-16 16:16:06 | 2024-11-16 16:16:06 |
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++;
res=s[i]-1;
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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
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: 109ms
memory: 3656kb
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:
2 2 32 5 4 14 22 28 40 3 22 46 64 7 1 7 24 30 36 54 63 3 3 14 30 5 1 11 30 41 47 4 13 27 34 46 1 51 1 27 1 22 1 62 5 24 33 42 47 60 2 3 31 3 11 19 29 3 2 15 33 2 30 42 3 2 17 59 4 -3 6 19 32 2 53 65 3 49 58 65 4 44 60 70 78 1 77 4 1 11 15 21 5 3 7 17 36 48 2 1 44 -1 2 -74 2 4 8 9 18 32 3 25 27 43 2 ...
result:
wrong answer There is no stripe covering red cell 3 (test case 2)