QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#731421#9574. Stripsucup-team1134#AC ✓90ms7604kbC++233.4kb2024-11-10 03:41:232024-11-10 03:41:24

Judging History

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

  • [2024-11-10 03:41:24]
  • 评测
  • 测评结果:AC
  • 用时:90ms
  • 内存:7604kb
  • [2024-11-10 03:41:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005;
const ll INF=15LL<<58;

vi solve(int L,vi pos,int W){
    vll S;
    int la=0;
    for(int i=0;i<si(pos);i++){
        if(la<=pos[i]-1) S.pb(mp(la,pos[i]-1));
        la=pos[i];
    }
    S.pb(mp(la,L));
    
    //for(auto [a,b]:S) cout<<a<<" "<<b<<endl;
    
    //cout<<L<<" "<<W<<endl;
    ll N=si(S);
    vector<ll> mi(N,INF),l(N),r(N),dis(N,INF);
    for(int i=0;i<N;i++){
        l[i]=S[i].fi;
        r[i]=S[i].se;
    }
    mi[0]=dis[0]=0;
    vii par(N);
    
    for(int i=0;i<N;i++){
        if(mi[i]==INF) continue;
        auto it=lower_bound(all(S),mp(mi[i]+W,-1LL));it--;
        ll a=mi[i]+W,b=r[i]+W;
        for(int j=it-S.begin();j<N;j++){
            ll x=max(l[j],a),y=min(r[j],b);
            if(x<=y){
                if(chmin(mi[j],x)){
                    if(chmin(dis[j],dis[i]+1)){
                        par[j]=mp(i,x);
                    }
                }
            }
            if(b<l[j]) break;
        }
    }
    if(mi[N-1]==INF) return {-1};
    else{
        int now=N-1;
        vi res;
        while(now){
            res.pb(par[now].se);
            now=par[now].fi;
        }
        //cout<<si(res)<<" "<<dis[N-1]<<endl;
        return res;
    }
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int Q;cin>>Q;
    while(Q--){
        int N,M,K,W;cin>>N>>M>>K>>W;
        vii S;
        S.pb(mp(0,0));
        S.pb(mp(W+1,0));
        for(int i=0;i<N;i++){
            int x;cin>>x;
            S.pb(mp(x,1));
        }
        for(int i=0;i<M;i++){
            int x;cin>>x;
            S.pb(mp(x,0));
        }
        sort(all(S));
        int ans=0;
        int i=0;
        vi res;
        while(i<si(S)){
            if(S[i].se==0){
                int j=i+1;
                while(j<si(S)&&S[j].se==1) j++;
                vi Z;
                for(int k=i+1;k<j;k++) Z.pb(S[k].fi-S[i].fi);
                auto X=solve(S[j].fi-S[i].fi-1,Z,K);
                if(si(X)&&X[0]==-1){
                    ans=-1;
                    break;
                }
                for(int x:X) res.pb(x+S[i].fi-(K-1));
                i=j;
            }else{
                assert(false);
            }
        }
        
        if(ans==-1){
            cout<<-1<<"\n";
        }else{
            cout<<si(res)<<"\n";
            for(int x:res) cout<<x<<" ";
            cout<<"\n";
        }
        
        
    }
}



这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

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 9 6 14 
-1
2
1 4 
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: 0
Accepted
time: 46ms
memory: 3660kb

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 
7
4 3 14 22 40 36 28 
3
22 46 64 
8
7 1 24 20 30 36 54 63 
3
3 14 30 
6
30 11 7 1 47 41 
4
14 34 27 47 
2
65 42 
1
27 
1
9 
1
62 
5
24 42 33 60 47 
2
3 31 
3
19 11 29 
3
2 15 33 
3
30 25 42 
3
2 17 59 
4
21 11 1 32 
2
65 53 
3
49 58 65 
3
60 43 78 
1
78 
4
1 11 21 15 
5
3 7 36 17 48 
2
1 44 ...

result:

ok ok 11000 cases (11000 test cases)

Test #3:

score: 0
Accepted
time: 62ms
memory: 7076kb

input:

2
62980 100000 9859 200000
132897 135912 27509 54599 183887 53114 127233 138596 120860 52471 83158 110644 114040 34102 100501 94779 188044 118947 57443 93009 179886 117863 142316 103026 133746 181956 88732 133751 178946 135462 99588 142382 116231 142902 98641 93039 34860 180746 34292 64655 31584 265...

output:

10
25298 45553 55916 80278 91309 101654 112655 127053 138336 178309 
10
19003028 88441083 141717798 296180043 362424389 454856685 535769141 620489184 771756205 925304609 

result:

ok ok 2 cases (2 test cases)

Test #4:

score: 0
Accepted
time: 62ms
memory: 6860kb

input:

2
62968 100000 987 200000
132608 47259 159851 136656 33393 145766 92631 125475 63424 186957 111759 164400 22296 95239 28164 39213 176169 72721 179002 29390 26931 55261 57111 143625 62022 48092 13696 31056 31569 136324 120007 167521 106377 119894 48641 106130 151757 146461 151941 92629 57328 134514 1...

output:

100
562 1592 5467 9868 11009 13012 14623 16508 20465 21483 24037 26079 27895 29239 30705 32052 33064 34282 38471 40932 42029 43429 44471 45848 47154 48454 51256 52449 55048 56388 58340 60318 61620 62764 64617 66496 67760 69515 70897 72155 74261 76183 77224 78525 83084 85061 87039 88856 91678 92834 9...

result:

ok ok 2 cases (2 test cases)

Test #5:

score: 0
Accepted
time: 52ms
memory: 6408kb

input:

2
11000 100000 11 200000
163012 113063 193436 164804 38223 97954 77455 12645 65893 7472 154060 115066 197136 68157 57696 125883 36460 36327 2594 182329 52863 9384 142218 108307 164812 102263 68023 123052 114544 38027 42624 82629 131406 110330 63104 198666 154174 168712 164172 28565 120683 174248 170...

output:

1000
263 350 1048 1037 1158 1258 1339 1797 1837 1856 2473 2512 2593 2721 2807 3624 3751 3893 4073 4577 4984 5418 5458 5817 6409 6723 7120 7320 7467 7736 7999 8249 8406 8520 8912 8926 9034 9293 9337 9326 9377 9461 9479 9529 9557 9926 10040 10424 10570 10754 10815 11241 11271 11390 11495 11703 11824 1...

result:

ok ok 2 cases (2 test cases)

Test #6:

score: 0
Accepted
time: 68ms
memory: 7044kb

input:

2
60562 100000 9 200000
124614 82957 175069 159802 77713 148208 87119 195619 137203 187199 151696 49407 92632 129159 22947 9508 83213 155794 8801 14455 4343 187591 112872 118191 84055 164173 127507 13848 193356 103420 67764 102061 151883 129600 112204 64020 118263 44490 15496 61703 177926 140419 918...

output:

9999
10 24 39 54 66 98 136 127 175 189 221 237 249 263 300 350 371 383 402 414 432 442 458 474 487 511 522 533 555 581 592 612 656 669 685 696 706 748 774 791 829 883 903 930 948 1015 1035 1046 1076 1103 1122 1151 1162 1234 1262 1252 1276 1286 1297 1312 1326 1361 1384 1398 1408 1429 1441 1472 1487 1...

result:

ok ok 2 cases (2 test cases)

Test #7:

score: 0
Accepted
time: 90ms
memory: 7604kb

input:

2
78636 100000 2 1000000
160618 689882 425029 248098 24811 473647 831221 372052 602440 158077 883901 645470 489547 863556 32157 371442 621866 941885 650516 873053 188342 224449 770318 464999 453057 304754 700410 82432 583687 478953 393561 989660 199977 458427 411530 814363 964896 69063 874312 224036...

output:

62519
25 20 17 13 64 104 101 131 147 167 188 216 236 257 275 270 298 289 286 284 280 345 374 361 386 416 408 443 441 438 433 429 427 454 462 474 471 500 495 524 570 567 556 637 628 649 655 668 693 741 763 758 771 841 836 818 809 868 862 899 913 938 958 967 987 1001 1010 1039 1022 1059 1057 1082 1135...

result:

ok ok 2 cases (2 test cases)

Extra Test:

score: 0
Extra Test Passed