QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#805604#9574. StripsvictoryAC#WA 31ms3644kbC++174.9kb2024-12-08 17:32:412024-12-08 17:32:41

Judging History

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

  • [2024-12-08 17:32:41]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:3644kb
  • [2024-12-08 17:32:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pos string::npos
#define endl '\n'
#define inf 1e18
typedef unsigned long long ull;
const int mod = 1e9+7;
const int N = 1e6+10;
const int Maxn = 2e5+5;
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
int Inv[N],F[N];//组合数C2
int gcd(int a,int b){ return b == 0 ? a : gcd(b,a%b);}
int lcm(int a,int b){return (a/gcd(a,b)*b);}
int km(int a,int b,int mod)
{int ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;}
int km1(int a,int b,int mod)//指数取模,2^2^i,单求2^i要取模MOD-1
{int ans=1;mod--;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;}
int C(int a,int b,int p){if(b>a) return 0;int res=1;for(int i=b,j=a;i>=1;i--,j--){res=res*j%p;res=res*km(i,p-2,p)%p;}return res;}
int Lucas(int a,int b,int p){if(a<p&&b<p) return C(a,b,p);return C(a%p,b%p,p)*Lucas(a/p,b/p,p)%p;}
int C2(int a,int b,int p){return F[a]*Inv[a-b]%p*Inv[b]%p;}
void C2init(int n,int p){n--;F[0]=F[1]=1;for(int i=2;i<=n;i++)F[i]=F[i-1]*i%p;Inv[n]=km(F[n],p-2,p);for(int i=n-1;i>=0;i--)Inv[i]=Inv[i+1]*(i+1)%p;}
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
struct edge{
    int v,w;
};
struct matrix{
    int c[5][5];
    matrix(){memset(c,0,sizeof c);}
}A,B;
matrix operator*(matrix &x,matrix &y){
    matrix t;
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            for(int k=1;k<=4;k++){
                //t.c[i][j]=(t.c[i][j]+mul(x.c[i][k],y.c[k][j]))%m;
                t.c[i][j]=(t.c[i][j]+(x.c[i][k]*y.c[k][j])%mod)%mod;
            }
        }
    }
    return t;
}
void km2(int k){
    while(k){
        if(k&1) A=A*B;
        B=B*B;
        k>>=1;
    }
}
int n,m,k,q,w;
void solve() 
{
    cin>>n>>m>>k>>w;
    vector<int> red,blk;
    for(int i=1;i<=n;i++) {
        int x;cin>>x;
        red.push_back(x);
    }
    for(int i=1;i<=m;i++){
        int x;cin>>x;
        blk.push_back(x);
    }
    int l=0,cnt=0,num=0;
    sort(red.begin(),red.end());
    sort(blk.begin(),blk.end());
    vector<vector<int>> ve(n+10,vector<int>());
    for(int i=0;i<blk.size();i++){
        int r=blk[i],sb=0;
        if(cnt==red.size()) break;
        while(red[cnt]<r&&cnt<red.size()){
            sb++;
            ve[num].push_back(red[cnt]);
            cnt++;
        }
        if(sb==0) continue;
        ve[num].push_back(l);
        ve[num].push_back(r);
        l=r;
        sort(ve[num].begin(),ve[num].end());
        num++;
    }
    if(cnt!=red.size()){
        for(int i=cnt;i<red.size();i++){
            ve[num].push_back(red[i]);
        }
        ve[num].push_back(l);
        ve[num].push_back(w+1);
        sort(ve[num].begin(),ve[num].end());
        num++;
    }
    bool ok=1;
    vector<pii> ans;
    /*for(int i=0;i<num;i++){
        for(auto tt:ve[i]) cout<<tt<<" ";
        cout<<endl;
    }*/
    for(int i=0;i<num;i++){
        if(!ok) break;
        vector<pii> res;
        int cd=ve[i][1]-ve[i][0]-1,srt=-1,end=0;
        for(int j=1;j<ve[i].size()-1;j++){
            if(srt==-1) srt=ve[i][j];
            else if(end>=ve[i][j]) continue;
            else srt=ve[i][j];
            res.push_back({srt,srt+k-1});
            end=max(end,srt+k-1);
            //for(auto kk:res) cout<<kk.first<<" ";
            //cout<<endl;
        }
        //cout<<end<<endl;
        if(end<ve[i][ve[i].size()-1]){
            for(auto tt:res) ans.push_back(tt);
        }
        else{
            bool cok=0;
            int cd1=end-ve[i][ve[i].size()-1]+1,end=-1;
            vector<pii> rev;
            for(int k=res.size()-1;k>=0;k--) {
                //cout<<res[k].second<<endl;
                if(end>res[k].second||cok){
                    cok=1;
                    rev.push_back({res[k].first,res[k].second});
                    continue;
                }
                rev.push_back({res[k].first-cd1,res[k].second-cd1});
                end=res[k].first-cd1;
            }
            if(end>ve[i][0]) cok=1;
            if(cok&&rev[0].second>=ve[i][ve[i].size()-2]){
                for(int i=rev.size()-1;i>=0;i--) ans.push_back({rev[i].first,rev[i].second});
            }
            else {
                ok=0;
                //cout<<i<<endl;
            }
        }
    }
    if(!ok) cout<<-1<<endl;
    else{
        cout<<ans.size()<<endl;
        for(auto tt:ans) cout<<tt.first<<" ";
        cout<<endl;
    }
}
signed main()
{
    ios;
    int T=1;
    //C2init(N,mod);
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3504kb

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
2 7 10 14 
-1
2
1 5 
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 31ms
memory: 3644kb

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
3 32 
7
3 4 14 22 28 36 40 
3
32 48 66 
8
3 9 22 26 31 38 54 65 
3
5 15 30 
6
1 8 12 31 41 47 
4
17 30 39 49 
2
52 67 
1
27 
1
22 
1
62 
5
24 33 43 48 60 
2
4 31 
3
11 20 31 
3
3 16 33 
3
25 30 42 
3
3 17 60 
-1
2
54 66 
3
50 59 65 
3
50 62 78 
1
81 
4
2 11 16 23 
5
3 7 17 36 49 
2
1 45 
2
7 25 
1...

result:

wrong answer Participant didn't find a solution but the jury found one. (test case 18)