QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#746343#9574. Stripssurenjamts#RE 0ms0kbC++172.2kb2024-11-14 14:18:572024-11-14 14:18:59

Judging History

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

  • [2024-11-14 14:18:59]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-11-14 14:18:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#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();
      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();
                if(mid + k <= dp[next]) l = mid;
                else r = mid;
           }
           if(l <= lt){
              return -1;
           }

           dp[i] = l;
      }

      int cur = dp[0];
      ans.push_back(cur);
      for(int i = 1; i < n; i++){
         if(cur + k >= red[i]) continue;
         else {
              cur = dp[i];
              ans.push_back(cur);
         }
      }
}
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){
             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: 0
Runtime Error

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:


result: