QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#728446#9574. Stripsucup-team112#AC ✓64ms10896kbC++2013.6kb2024-11-09 15:11:392024-11-09 15:11:40

Judging History

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

  • [2024-11-09 15:11:40]
  • 评测
  • 测评结果:AC
  • 用时:64ms
  • 内存:10896kb
  • [2024-11-09 15:11:39]
  • 提交

answer


//#define _GLIBCXX_DEBUG

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
using namespace std;


#ifdef LOCAL
#include <debug_print.hpp>
#define OUT(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define OUT(...) (static_cast<void>(0))
#endif

#define endl '\n'
#define lfs cout<<fixed<<setprecision(15)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)

namespace template_tute{
  using ll = long long;
  using ld = long double;
  const ll MOD1 = 1e9+7;
  const ll MOD9 = 998244353;
  const ll INF = 4.1e18;
  using P = pair<ll, ll>;
  template<typename T> using PQ = priority_queue<T>;
  template<typename T> using QP = priority_queue<T,vector<T>,greater<T>>;
  template<typename T1, typename T2>bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
  template<typename T1, typename T2>bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
  ll median(ll a,ll b, ll c){return a+b+c-max<ll>({a,b,c})-min<ll>({a,b,c});}
  void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
  void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
  void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
  template<typename T1,typename T2>void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
  template<typename T1,typename T2,typename T3>void anss(T1 x,T2 y,T3 z){ans(x!=y,x,z);};  
  template<typename T>void debug(const T &v,ll h,ll w,string sv=" "){for(ll i=0;i<h;i++){cout<<v[i][0];for(ll j=1;j<w;j++)cout<<sv<<v[i][j];cout<<endl;}};
  template<typename T>void debug(const T &v,ll n,string sv=" "){if(n!=0)cout<<v[0];for(ll i=1;i<n;i++)cout<<sv<<v[i];cout<<endl;};
  template<typename T>void debug(const vector<T>&v){debug(v,v.size());}
  template<typename T>void debug(const vector<vector<T>>&v){for(auto &vv:v)debug(vv,vv.size());}
  template<typename T>void debug(stack<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(queue<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(deque<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop_front();}cout<<endl;}
  template<typename T>void debug(PQ<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(QP<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(const set<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
  template<typename T>void debug(const multiset<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
  template<typename T,size_t size>void debug(const array<T, size> &a){for(auto z:a)cout<<z<<" ";cout<<endl;}
  template<typename T,typename V>void debug(const map<T,V>&v){for(auto z:v)cout<<"["<<z.first<<"]="<<z.second<<",";cout<<endl;}
  template<typename T>vector<vector<T>>vec(ll x, ll y, T w){vector<vector<T>>v(x,vector<T>(y,w));return v;}
  vector<ll>dx={1,-1,0,0,1,1,-1,-1};vector<ll>dy={0,0,1,-1,1,-1,1,-1};
  template<typename T>vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
  template<typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
  template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2>&p){return os << "(" << p.first << "," << p.second << ")";}
  template<typename T>ostream &operator<<(ostream &os, const vector<T> &v){os<<"[";for(auto &z:v)os << z << ",";os<<"]"; return os;}
  template<typename T>void rearrange(vector<int>&ord, vector<T>&v){
    auto tmp = v;
    for(int i=0;i<tmp.size();i++)v[i] = tmp[ord[i]];
  }
  template<typename Head, typename... Tail>void rearrange(vector<int>&ord,Head&& head, Tail&&... tail){
    rearrange(ord, head);
    rearrange(ord, tail...);
  }
  template<typename T> vector<int> ascend(const vector<T>&v){
    vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],i)<make_pair(v[j],j);});
    return ord;
  }
  template<typename T> vector<int> descend(const vector<T>&v){
    vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],-i)>make_pair(v[j],-j);});
    return ord;
  }
  template<typename T> vector<T> inv_perm(const vector<T>&ord){
    vector<T>inv(ord.size());
    for(int i=0;i<ord.size();i++)inv[ord[i]] = i;
    return inv;
  }
  ll FLOOR(ll n,ll div){assert(div>0);return n>=0?n/div:(n-div+1)/div;}
  ll CEIL(ll n,ll div){assert(div>0);return n>=0?(n+div-1)/div:n/div;}
  ll digitsum(ll n){ll ret=0;while(n){ret+=n%10;n/=10;}return ret;}
  ll modulo(ll n,ll d){return (n%d+d)%d;};
  template<typename T>T min(const vector<T>&v){return *min_element(v.begin(),v.end());}
  template<typename T>T max(const vector<T>&v){return *max_element(v.begin(),v.end());}
  template<typename T>T acc(const vector<T>&v){return accumulate(v.begin(),v.end(),T(0));};
  template<typename T>T reverse(const T &v){return T(v.rbegin(),v.rend());};
  //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  int popcount(ll x){return __builtin_popcountll(x);};
  int poplow(ll x){return __builtin_ctzll(x);};
  int pophigh(ll x){return 63 - __builtin_clzll(x);};
  template<typename T>T poll(queue<T> &q){auto ret=q.front();q.pop();return ret;};
  template<typename T>T poll(priority_queue<T> &q){auto ret=q.top();q.pop();return ret;};
  template<typename T>T poll(QP<T> &q){auto ret=q.top();q.pop();return ret;};
  template<typename T>T poll(stack<T> &s){auto ret=s.top();s.pop();return ret;};
  ll MULT(ll x,ll y){if(LLONG_MAX/x<=y)return LLONG_MAX;return x*y;}
  ll POW2(ll x, ll k){ll ret=1,mul=x;while(k){if(mul==LLONG_MAX)return LLONG_MAX;if(k&1)ret=MULT(ret,mul);mul=MULT(mul,mul);k>>=1;}return ret;}
  ll POW(ll x, ll k){ll ret=1;for(int i=0;i<k;i++){if(LLONG_MAX/x<=ret)return LLONG_MAX;ret*=x;}return ret;}
  std::ostream &operator<<(std::ostream &dest, __int128_t value) {
    std::ostream::sentry s(dest);
    if (s) {
      __uint128_t tmp = value < 0 ? -value : value;
      char buffer[128];
      char *d = std::end(buffer);
      do {
        --d;
        *d = "0123456789"[tmp % 10];
        tmp /= 10;
      } while (tmp != 0);
      if (value < 0) {
        --d;
        *d = '-';
      }
      int len = std::end(buffer) - d;
      if (dest.rdbuf()->sputn(d, len) != len) {
        dest.setstate(std::ios_base::badbit);
      }
    }
    return dest;
  }
  namespace converter{
    int dict[500];
    const string lower="abcdefghijklmnopqrstuvwxyz";
    const string upper="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string digit="0123456789";
    const string digit1="123456789";
    void regi_str(const string &t){
      for(int i=0;i<t.size();i++){
        dict[t[i]]=i;
      }
    }
    void regi_int(const string &t){
      for(int i=0;i<t.size();i++){
        dict[i]=t[i];
      }
    }
    vector<int>to_int(const string &s,const string &t){
      regi_str(t);
      vector<int>ret(s.size());
      for(int i=0;i<s.size();i++){
        ret[i]=dict[s[i]];
      }
      return ret;
    }
    vector<int>to_int(const string &s){
      auto t=s;
      sort(t.begin(),t.end());
      t.erase(unique(t.begin(),t.end()),t.end());
      return to_int(s,t);
    }
    
    vector<vector<int>>to_int(const vector<string>&s,const string &t){
      regi_str(t);
      vector<vector<int>>ret(s.size(),vector<int>(s[0].size()));
      for(int i=0;i<s.size();i++){
        for(int j=0;j<s[0].size();j++){
          ret[i][j]=dict[s[i][j]];
        }
      }
      return ret;
    }
    vector<vector<int>>to_int(const vector<string>&s){
      string t;
      for(int i=0;i<s.size();i++){
        t+=s[i];
      }
      sort(t.begin(),t.end());t.erase(unique(t.begin(),t.end()),t.end());
      return to_int(s,t);
    }
    string to_str(const vector<int>&s,const string &t){
      regi_int(t);
      string ret;
      for(auto z:s)ret+=dict[z];
      return ret;
    }
    vector<string> to_str(const vector<vector<int>>&s,const string &t){
      regi_int(t);
      vector<string>ret(s.size());
      for(int i=0;i<s.size();i++){
        for(auto z:s[i])ret[i]+=dict[z];
      }
      return ret;
    }
  }
  template< typename T = int >
  struct edge {
    int to;
    T cost;
    int id;
    edge():to(-1),id(-1){};
    edge(int to, T cost = 1, int id = -1):to(to), cost(cost), id(id){}
    operator int() const { return to; }
  };

  template<typename T>
  using Graph = vector<vector<edge<T>>>;
  template<typename T>
  Graph<T>revgraph(const Graph<T> &g){
    Graph<T>ret(g.size());
    for(int i=0;i<g.size();i++){
      for(auto e:g[i]){
        int to = e.to;
        e.to = i;
        ret[to].push_back(e);
      }
    }
    return ret;
  }
  template<typename T>
  Graph<T> readGraph(int n,int m,int indexed=1,bool directed=false,bool weighted=false){
    Graph<T> ret(n);
    for(int es = 0; es < m; es++){
      int u,v;
      T w=1;
      cin>>u>>v;u-=indexed,v-=indexed;
      if(weighted)cin>>w;
      ret[u].emplace_back(v,w,es);
      if(!directed)ret[v].emplace_back(u,w,es);
    }
    return ret;
  }
  template<typename T>
  Graph<T> readParent(int n,int indexed=1,bool directed=true){
    Graph<T>ret(n);
    for(int i=1;i<n;i++){
      int p;cin>>p;
      p-=indexed;
      ret[p].emplace_back(i);
      if(!directed)ret[i].emplace_back(p);
    }
    return ret;
  }
}
using namespace template_tute;

template< typename Monoid ,typename F>
struct SegmentTree {
  int sz, n;
  vector< Monoid > seg;
  const F f;
  const Monoid M1;

  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1), n(n){
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }

  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  Monoid query(int a, int b) {
    if(a>=b)return M1;
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }

  template< typename C >
  int find_subtree(int a, const C &check, Monoid &M, bool type) {
    while(a < sz) {
      Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
      if(check(nxt)) a = 2 * a + type;
      else M = nxt, a = 2 * a + 1 - type;
    }
    return a - sz;
  }
  //[a,x]が条件を満たす最初のx,満たさなければn
  template< typename C >
  int find_first(int a, const C &check) {
    Monoid L = M1;
    if(a <= 0) {
      if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
      return n;
    }
    int b = sz;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) {
        Monoid nxt = f(L, seg[a]);
        if(check(nxt)) return find_subtree(a, check, L, false);
        L = nxt;
        ++a;
      }
    }
    return n;
  }
  //[x,b)が条件を満たす最後のx,満たさなければ-1
  template< typename C >
  int find_last(int b, const C &check) {
    Monoid R = M1;
    if(b >= sz) {
      if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
      return -1;
    }
    int a = sz;
    for(b += sz; a < b; a >>= 1, b >>= 1) {
      if(b & 1) {
        Monoid nxt = f(seg[--b], R);
        if(check(nxt)) return find_subtree(b, check, R, true);
        R = nxt;
      }
    }
    return -1;
  }
  void print(){
    for(ll i=0;i<n;i++)if((*this)[i]==M1)cout<<"x ";else cout<<(*this)[i]<<" ";
    cout<<endl;
  }
};

namespace range_min{
  using M=ll;
  auto f=[](M x,M y){
    return min(x,y);
  };
  SegmentTree<M,decltype(f)>make(int n){
    return {n,f,INF};
  }
}

void solve(){
	ll res=0,buf=0;
  bool judge = true;
  ll n,m,k,w;cin>>n>>m>>k>>w;
  vector<P>t;
  rep(i,0,n){
    ll a;cin>>a;a--;
    t.EB(a,1);
  }
  rep(i,0,m){
    ll b;cin>>b;b--;
    t.EB(b,2);
  }
  sort(ALL(t));
  auto solve=[&](vector<ll>a)->vector<ll> {
    ll n=a.size();
    ll pre=-INF;
    vector<ll>ret;
    rep(i,0,n-1){
      if(pre+k<=a[i]){
        pre=a[i];
        ret.PB(a[i]);
      }
    }
    ll last=a[n-1];
    rrep(i,0,ret.size()){
      chmin(ret[i],last-k);
      last=ret[i];
    }
    //OUT(a,ret);
    return ret;
  };
  vector<ll>b;
  vector<ll>ret;
  //OUT(t);
  t.EB(-1,2);
  t.EB(w,2);
  sort(ALL(t));
  ll pre=-1;
  //OUT(t);
  for(auto z:t){
    if(z.se==2){
      //OUT(i,b);
      b.PB(z.fi-pre-1);
      auto tmp=solve(b);
      if(!tmp.empty()&&tmp[0]<0){
        cout<<-1<<endl;
        return;
      }
      for(auto z:tmp){
        ret.PB(pre+z+2);
      }
      pre=z.fi;
      b.clear();
    }
    else{
      b.PB(z.fi-pre-1);
    }
  }
  sort(ALL(ret));
  cout<<ret.size()<<endl;
  debug(ret);
}

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  int T = 1;
  cin>>T;
  while(T--){
    solve();
  }
  return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 27ms
memory: 3628kb

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
4
1 11 21 33
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
4
4
9 18 29 32...

result:

ok ok 11000 cases (11000 test cases)

Test #3:

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

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
19008292 88443553 141719421 296188093 362431412 454873168 535773187 620493211 771767782 925311474

result:

ok ok 2 cases (2 test cases)

Test #4:

score: 0
Accepted
time: 59ms
memory: 10660kb

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: 53ms
memory: 10552kb

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 1037 1048 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 9326 9337 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: 59ms
memory: 10896kb

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 127 136 175 189 221 237 249 263 300 350 371 383 402 414 432 442 458 474 487 511 522 533 555 581 592 612 657 669 685 696 706 748 774 791 829 883 903 930 948 1015 1035 1046 1076 1103 1122 1151 1162 1234 1253 1262 1276 1286 1297 1312 1326 1361 1384 1398 1409 1429 1441 1472 1487 1...

result:

ok ok 2 cases (2 test cases)

Test #7:

score: 0
Accepted
time: 64ms
memory: 10528kb

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
13 17 21 26 65 102 105 132 148 168 189 217 237 257 270 276 280 285 287 290 299 346 361 375 386 408 416 427 430 433 439 441 444 455 463 472 475 496 501 525 557 568 571 629 637 650 656 669 694 742 759 764 772 809 819 837 842 863 869 899 913 939 958 968 988 1002 1010 1022 1040 1057 1060 1082 1097...

result:

ok ok 2 cases (2 test cases)

Extra Test:

score: 0
Extra Test Passed