QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#557508#9252. Penguins in Refrigeratorucup-team159WA 42ms11176kbC++2311.5kb2024-09-11 10:02:032024-09-11 10:02:03

Judging History

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

  • [2024-09-11 10:02:03]
  • 评测
  • 测评结果：WA
  • 用时：42ms
  • 内存：11176kb
查看
  • [2024-09-11 10:02:03]
  • 提交

answer

#line 1 "K.cpp"
// #pragma GCC target("avx2,avx512f,avx512vl,avx512bw,avx512dq,avx512cd,avx512vbmi,avx512vbmi2,avx512vpopcntdq,avx512bitalg,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("Ofast")

#line 2 "/home/sigma/comp/library/template.hpp"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb push_back
#define eb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> bool chmax(T& x, U y){
	if(x<y){ x=y; return true; }
	return false;
}
template<class T,class U> bool chmin(T& x, U y){
	if(y<x){ x=y; return true; }
	return false;
}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();}
template<class T>
V<T> Vec(size_t a) {
    return V<T>(a);
}
template<class T, class... Ts>
auto Vec(size_t a, Ts... ts) {
  return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...));
}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ~ ";
	dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif

template<class D> D divFloor(D a, D b){
	return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}
template<class D> D divCeil(D a, D b) {
	return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}
#line 1 "/home/sigma/comp/ac-library/atcoder/segtree.hpp"



#line 8 "/home/sigma/comp/ac-library/atcoder/segtree.hpp"

#line 1 "/home/sigma/comp/ac-library/atcoder/internal_bit.hpp"



#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder


#line 10 "/home/sigma/comp/ac-library/atcoder/segtree.hpp"

namespace atcoder {

#if __cplusplus >= 201703L

template <class S, auto op, auto e> struct segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");

#else

template <class S, S (*op)(S, S), S (*e)()> struct segtree {

#endif

  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder


#line 6 "K.cpp"
using namespace atcoder;

template<unsigned int mod_>
struct ModInt{	
	using uint = unsigned int;
	using ll = long long;
	using ull = unsigned long long;

	constexpr static uint mod = mod_;

	uint v;
	ModInt():v(0){}
	ModInt(ll _v):v(normS(_v%mod+mod)){}
	explicit operator bool() const {return v!=0;}
	static uint normS(const uint &x){return (x<mod)?x:x-mod;}		// [0 , 2*mod-1] -> [0 , mod-1]
	static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
	ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
	ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
	ModInt operator-() const { return make(normS(mod-v)); }
	ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
	ModInt operator/(const ModInt& b) const { return *this*b.inv();}
	ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
	ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
	ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
	ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
	ModInt& operator++(int){ return *this=*this+1;}
	ModInt& operator--(int){ return *this=*this-1;}
	template<class T> friend ModInt operator+(T a, const ModInt& b){ return (ModInt(a) += b);}
	template<class T> friend ModInt operator-(T a, const ModInt& b){ return (ModInt(a) -= b);}
	template<class T> friend ModInt operator*(T a, const ModInt& b){ return (ModInt(a) *= b);}
	template<class T> friend ModInt operator/(T a, const ModInt& b){ return (ModInt(a) /= b);}
	ModInt pow(ll p) const {
		if(p<0) return inv().pow(-p);
		ModInt a = 1;
		ModInt x = *this;
		while(p){
			if(p&1) a *= x;
			x *= x;
			p >>= 1;
		}
		return a;
	}
	ModInt inv() const {		// should be prime
		return pow(mod-2);
	}
	// ll extgcd(ll a,ll b,ll &x,ll &y) const{
	// 	ll p[]={a,1,0},q[]={b,0,1};
	// 	while(*q){
	// 		ll t=*p/ *q;
	// 		rep(i,3) swap(p[i]-=t*q[i],q[i]);
	// 	}
	// 	if(p[0]<0) rep(i,3) p[i]=-p[i];
	// 	x=p[1],y=p[2];
	// 	return p[0];
	// }
	// ModInt inv() const {
	// 	ll x,y;
	// 	extgcd(v,mod,x,y);
	// 	return make(normS(x+mod));
	// }

	bool operator==(const ModInt& b) const { return v==b.v;}
	bool operator!=(const ModInt& b) const { return v!=b.v;}
	bool operator<(const ModInt& b) const { return v<b.v;}
	friend istream& operator>>(istream &o,ModInt& x){
		ll tmp;
		o>>tmp;
		x=ModInt(tmp);
		return o;
	}
	friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
	// friend ostream& operator<<(ostream &o,const ModInt& x){
	// 	for(int b=1;b<=1000;b++){
	// 		ModInt ib = ModInt(b).inv();
	// 		for(int a=-1000;a<=1000;a++){
	// 			if(ModInt(a) * ib == x){
	// 				return o << a << "/" << b;
	// 			}
	// 		}
	// 	}
	// 	return o<<x.v;
	// }
};
using mint = ModInt<1000000007>;

struct Small{
	int l,r,id,w;
	friend ostream& operator<<(ostream &o,const Small& x){ return o<<"__["<<x.l<<","<<x.r<<"], id = " << x.id << ", w = " << x.w<<"__";}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);

	int N,W; cin >> N >> W;
	V<int> p(N), w(N);
	rep(i,N){
		int pi; cin >> pi; pi--;
		p[pi] = i;
	}
	rep(i,N){
		int wi; cin >> wi;
		w[p[i]] = wi;
	}
	reverse(all(p)); reverse(all(w));

	V<int> big;
	rep(i,N) if(w[i]*2 > W) big.eb(i);
	int K = si(big);
	V<Small> small;
	{
		segtree<int,[&](int x,int y){return max(x,y);},[&](){return -1;}> seg(K);
		rep(k,K) seg.set(k,w[big[k]]);
		int g = 0;
		rep(i,N){
			if(w[i]*2 <= W){
				int l = seg.min_left(g,[&](int v){return v+w[i] <= W;});
				int r = seg.max_right(g,[&](int v){return v+w[i] <= W;});
				// [l,r]
				small.pb({l,r,p[i],w[i]});
			}else{
				g++;
			}
		}
	}
	// count
	{
		segtree<int,[&](int x,int y){return x+y;},[&](){return 0;}> seg(K+1);
		rep(k,K+1) seg.set(k,1);
		sort(all(small),[&](Small& x, Small& y){return x.w > y.w;});
		show(small);
		mint res = 1;
		for(auto s: small){
			res *= seg.prod(s.l,s.r+1);
			seg.set(s.l, seg.get(s.l)+1);
		}
		cout << res << endl;
	}
	// lex
	{
		VV<int> l2ids(K+1),r2ids(K+1);
		for(auto s: small){
			l2ids[s.l].eb(s.id);
			r2ids[s.r].eb(s.id);
		}
		rep(k,K+1){
			sort(all(l2ids[k]));
			sort(all(r2ids[k]));
		}
		set<int> st;
		V<int> bigid;
		rep(k,K) bigid.eb(p[big[k]]);
		bigid.eb(1e9);
		V<int> ans;

		rep(k,K+1){
			for(int id: l2ids[k]) st.insert(id);
			while(!st.empty() && *st.begin() < bigid[k]){
				ans.eb(*st.begin());
				st.erase(st.begin());
			}
			for(int id: r2ids[k]){
				if(st.count(id)){
					ans.eb(id);
					st.erase(id);
				}
			}
			ans.eb(bigid[k]);
		}
		ans.pop_back();
		assert(si(ans) == N);
		rep(i,N) cout << ans[i]+1 << " ";
		cout << endl;
	}
}
源文件, 语言: C++23

詳細信息

Test #1:

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

input:

5 10
1 2 3 4 5
6 5 3 9 2

output:

3
5 4 2 1 3

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

5 10
1 2 3 4 5
2 4 3 3 8

output:

30
1 5 2 3 4

result:

ok 2 lines

Test #3:

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

input:

5 10
1 2 3 4 5
2 3 4 5 1

output:

120
1 2 3 4 5

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

5 10
1 2 3 4 5
2 3 4 5 6

output:

60
1 2 3 5 4

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 42ms
memory: 11176kb

input:

100000 96
1996 78922 45321 68844 32404 82013 66552 81163 17216 48170 35495 56660 13480 43118 23173 47257 50168 87069 26167 67231 31758 25694 61063 56642 8923 7727 54528 96554 38964 7604 6822 16256 45300 58869 31359 48638 87645 14779 81505 59585 89293 9291 7002 31810 84701 77648 78295 42595 11394 479...

output:

457992974
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

result:

ok 2 lines

Test #6:

score: -100
Wrong Answer
time: 32ms
memory: 8832kb

input:

100000 84
93330 3894 94859 22134 49668 30606 26739 82976 76701 56323 75537 7626 87226 20857 98177 21811 70827 75898 8111 48223 26186 64222 63002 79024 19126 41638 1048 43857 25379 19764 60207 27675 77665 66327 6274 34861 30287 13449 64505 51490 5804 65843 49014 85795 12365 31565 34411 71697 66568 28...

output:

524727018
17609 25144 28710 32650 37825 46810 58859 60458 64502 64892 67718 68948 79326 89737 90927 92556 23867 35681 66474 1358 11204 11811 12244 13655 25824 28444 29952 32443 33123 34067 81095 87426 89917 46675 4067 12286 14477 19728 25502 33176 50885 51062 54679 56377 57578 58025 67861 72282 7651...

result:

wrong answer 2nd lines differ - expected: '1723 2800 15421 26278 31659 42...6 87226 93330 98177 26739 49668', found: '17609 25144 28710 32650 37825 ... 88738 95200 95234 97528 97580 '
English 繁體中文 简体中文

伺服器時間: 2025-01-20 21:10:40 | 開源專案