QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#746431#9574. Stripssurenjamts#WA 33ms3752kbC++172.4kb2024-11-14 14:36:452024-11-14 14:36:54

Judging History

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

  • [2024-11-14 14:36:54]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:3752kb
  • [2024-11-14 14:36:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define S second
#define F first
vector<int> ans;
int k;
int comp(vector<int> red, int lt, int rt){
      if(rt == 0) return 0;
      int n = red.size();
      //cout << n << endl;
      vector<int> dp(n + 1);
      dp[n] = rt;
      for(int i = n - 1; i >=0; i--){
           int l = red[i] - k + 1;
           int r = red[i] + 1;

           if(red[i] >= dp[i + 1]){
               dp[i] = dp[i + 1];
               continue;
           }
           bool ok = 1;
           while(l + 1 < r){
                int mid = (l + r)/2;
                int next = lower_bound(red.begin() + i, red.end(), mid + k) - red.begin();
                assert(next <= n && next >= 0);
                if(mid + k <= dp[next]) l = mid;
                else r = mid;
           }

        //   cout << i <<  " " << l << endl;
           if(l <= lt){
              return -1;
           }

           dp[i] = l;
      }

      int cur = dp[0];
      ans.push_back(cur);
      for(int i = 1; i < n; i++){
           // cout << cur << " " << red[i] << endl;
         if(cur + k > red[i]) continue;
         else {
              cur = dp[i];
              ans.push_back(cur);
         }
      }

      return 0;
}
void solve(){
       ans.clear();
	   int n, m, w;
	   cin >> n >> m >> k >> w;
	   int a[n + 1];
	   int b[m + 1];

       vector<pair<int, bool>> v;
       v.emplace_back(0, 0);
	   for(int i = 0; i < n; i++) cin >> a[i], v.emplace_back(a[i], 1);
	   for(int j = 0; j < m; j++) cin >> b[j], v.emplace_back(b[j], 0);
	   v.emplace_back(w + 1, 0);

       sort(v.begin(), v.end());
       vector<int> red;
       int blackprev = 0;

       for(auto &[i, isred] : v){
         //   cout << i << " is red " << isred << endl;
             if(!isred){
                  if(comp(red, blackprev, i) == -1){
                        cout << "-1\n";
                        return;
                  }
                  blackprev = i;
                  red.clear();
             } else{
                  red.push_back(i);
             }
       }


       cout << ans.size() << '\n';
       for(auto i : ans){
           cout << i << " ";
       }
       cout << '\n';
}
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


    int t;  cin >> t; while(t--) solve();

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 33ms
memory: 3552kb

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:

9
1 3 10 19 20 30 32 38 54 
14
1 3 4 9 12 13 14 19 20 22 28 36 40 43 
7
4 7 21 32 48 62 66 
10
3 9 22 26 31 38 52 53 54 65 
9
2 5 10 12 13 15 27 28 30 
6
1 8 12 31 41 47 
8
3 4 7 17 26 30 39 49 
10
1 27 28 36 52 67 96 98 99 100 
6
9 17 21 31 45 46 
5
6 8 22 55 66 
7
13 15 32 39 62 72 77 
8
3 9 24 33...

result:

wrong answer Integer parameter [name=c] equals to 9, violates the range [-1, 3] (test case 1)