QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#755018#9574. StripsAlucardWA 109ms3656kbC++144.0kb2024-11-16 16:16:062024-11-16 16:16:06

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 16:16:06]
  • 评测
  • 测评结果:WA
  • 用时:109ms
  • 内存:3656kb
  • [2024-11-16 16:16:06]
  • 提交

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)