QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#558761#9252. Penguins in RefrigeratorzltWA 68ms104424kbC++143.4kb2024-09-11 18:26:192024-09-11 18:26:20

Judging History

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

  • [2024-09-11 18:26:20]
  • 评测
  • 测评结果:WA
  • 用时:68ms
  • 内存:104424kb
  • [2024-09-11 18:26:19]
  • 提交

answer

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

bool Mst;

const int maxn = 1000100;
const int logn = 21;
const int maxm = 21000100;
const ll mod = 1000000007;

int n, m, a[maxn], p[maxn], ind[maxm], nt, c[maxn], ls[maxn], rs[maxn], stk[maxn], top;
int f[logn][maxn], d[maxn], e[maxn];
ll ans = 1;

struct node {
	int i, p, x;
} b[maxn];

struct graph {
	int nxt[maxm], len, to[maxm], hd[maxm];
	
	inline void add_edge(int u, int v) {
		to[++len] = v;
		nxt[len] = hd[u];
		hd[u] = len;
		++ind[v];
	}
} T;

void cdq(int l, int r) {
	if (l == r) {
		return;
	}
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
	int u = 0;
	// printf("%d %d\n", l, r);
	// for (int i = l; i <= r; ++i) {
		// printf("i: %d %d %d %d\n", i, b[i].i, b[i].p, b[i].x);
	// }
	for (int i = r, j = l; i > mid; --i) {
		while (j <= mid && b[j].x + b[i].x < m) {
			int v = ++nt;
			if (u) {
				T.add_edge(u, v);
			}
			T.add_edge(b[j].i, v);
			u = v;
			++j;
		}
		if (u) {
			T.add_edge(u, b[i].i);
		}
	}
	inplace_merge(b + l, b + mid + 1, b + r + 1, [&](const node &a, const node &b) {
		return a.x < b.x;
	});
}

void dfs(int u) {
	int t = 0;
	if (ls[u]) {
		dfs(ls[u]);
		t += e[ls[u]];
	}
	if (rs[u]) {
		dfs(rs[u]);
		t += e[rs[u]];
	}
	t += (d[u] == u);
	for (int i = 1; i <= e[u]; ++i) {
		ans = ans * (t + i) % mod;
	}
	e[u] += t;
}

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1, x; i <= n; ++i) {
		scanf("%d", &x);
		p[x] = i;
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		b[i].i = i;
		b[i].p = p[i];
		b[i].x = m - a[i];
		c[p[i]] = a[i];
	}
	sort(b + 1, b + n + 1, [&](const node &a, const node &b) {
		return a.p > b.p || (a.p == b.p && a.x < b.x);
	});
	for (int i = 1; i <= n; ++i) {
		int k = top;
		while (k && c[stk[k]] < c[i]) {
			--k;
		}
		if (k) {
			rs[stk[k]] = i;
		}
		if (k < top) {
			ls[i] = stk[k + 1];
		}
		stk[++k] = i;
		top = k;
	}
	for (int i = 1; i <= n; ++i) {
		if (ls[i]) {
			f[0][ls[i]] = i;
		}
		if (rs[i]) {
			f[0][rs[i]] = i;
		}
	}
	for (int j = 1; j <= 20; ++j) {
		for (int i = 1; i <= n; ++i) {
			f[j][i] = f[j - 1][f[j - 1][i]];
		}
	}
	for (int i = 1; i <= n; ++i) {
		int p = i;
		for (int j = 20; ~j; --j) {
			if (f[j][p] && a[i] + a[f[j][p]] <= m) {
				p = f[j][p];
			}
		}
		d[i] = p;
		if (i != p) {
			++e[p];
		}
	}
	dfs(stk[1]);
	printf("%lld\n", ans);
	nt = n;
	cdq(1, n);
	priority_queue< int, vector<int>, greater<int> > pq;
	queue<int> q;
	for (int i = 1; i <= nt; ++i) {
		if (!ind[i]) {
			if (i <= n) {
				pq.push(i);
			} else {
				q.push(i);
			}
		}
	}
	while (q.size() || pq.size()) {
		int u;
		if (q.size()) {
			u = q.front();
			q.pop();
		} else {
			u = pq.top();
			pq.pop();
			printf("%d ", u);
		}
		for (int _ = T.hd[u]; _; _ = T.nxt[_]) {
			int v = T.to[_];
			if (!(--ind[v])) {
				if (v <= n) {
					pq.push(v);
				} else {
					q.push(v);
				}
			}
		}
	}
}

bool Med;

int main() {
	fprintf(stderr, "%.2lf MB\n", (&Mst - &Med) / 1048576.);
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

詳細信息

Test #1:

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

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

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

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

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: 40ms
memory: 74496kb

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: 68ms
memory: 104424kb

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:

675258115
1723 2800 15421 26278 31659 42502 42606 56945 60694 62369 70160 73990 80586 88502 89122 59690 27661 33622 94788 14089 1146 2690 3632 4491 5439 8588 17476 17922 18136 20123 24857 39523 18825 28520 30999 32947 36013 41413 43842 43919 54502 58104 60783 65767 69064 71878 74728 75343 76546 7807...

result:

wrong answer 1st lines differ - expected: '524727018', found: '675258115'