QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#557524#9252. Penguins in Refrigeratorucup-team159WA 46ms11560kbC++2311.6kb2024-09-11 10:09:232024-09-11 10:09:32

Judging History

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

  • [2024-09-11 10:09:32]
  • 评测
  • 测评结果：WA
  • 用时：46ms
  • 内存：11560kb
查看
  • [2024-09-11 10:09:23]
  • 提交

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;
	using P = pair<int,int>;
	V<int> p(N), ip(N), w(N);
	rep(i,N){
		int pi; cin >> pi; pi--;
		p[pi] = i; ip[i] = pi;
	}
	rep(i,N){
		int wi; cin >> wi;
		w[ip[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: 3792kb

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: 3824kb

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: 3824kb

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: 3788kb

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: 46ms
memory: 11560kb

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: 36ms
memory: 9160kb

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:

120390347
1358 17609 18290 26501 35681 58859 60458 66474 79326 92556 23867 81095 99165 28710 12244 72282 11204 11811 19728 29952 34067 37825 67861 87426 76518 4067 12286 25502 46675 50885 14477 51062 57578 58025 84745 89917 98967 83739 33176 79256 49220 64892 1209 25824 32650 33123 50323 54679 64502...

result:

wrong answer 1st lines differ - expected: '524727018', found: '120390347'
English 繁體中文 简体中文

服务器时间: 2025-01-20 21:08:14 | 开源项目