QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#278362#7778. Turning Permutationucup-team2303#WA 0ms3748kbC++172.5kb2023-12-07 15:08:302023-12-07 15:08:30

Judging History

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

  • [2023-12-07 15:08:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3748kb
  • [2023-12-07 15:08:30]
  • 提交

answer

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

#define PB emplace_back
#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define siz(a) ((int) a.size())

const int N = 50;
int a, b, s[N + 5], ans[N + 5], f[N + 5][N + 5], g[N + 5][N + 5], h[N + 5][2][2], C[N + 5][N + 5];

int calc() {
	int now = 0, res = 1;
	rep(l, 1, a) {
		if(s[l]) continue;
		int r = l;
		while(r + 1 <= a && !s[r + 1]) ++r;
		if((__int128) res * C[now + r - l + 1][now] > b) res = b + 1;
		else res *= C[now + r - l + 1][now];
		int tmp = h[r - l + 1][1][1];
		if(l == 1) tmp += h[r - l + 1][0][1];
		if(r == a) tmp += h[r - l + 1][1][0];
		if(l == 1 && r == a) tmp += h[r - l + 1][0][0];
		if((__int128) res * tmp > b) res = b + 1;
		else res *= tmp;
		now += r - l + 1;
		l = r;
	}
	return res;
}

signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> a >> b;
	rep(i, 0, a) {
		C[i][0] = 1;
		rep(j, 1, i) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
	}
	f[1][1] = g[1][1] = 1;
	h[1][0][0] = h[1][1][1] = 1;
	rep(i, 2, a) {
		rep(j, 1, i) {
			if(i & 1) {
				rep(k, 1, j - 1) {
					f[i][j] += f[i - 1][k];
					f[i][j] = min(f[i][j], b + 1);
				}
				h[i][1][1] += f[i][j];
				h[i][1][1] = min(h[i][1][1], b + 1);
			}
			else {
				rep(k, j, i - 1) {
					f[i][j] += f[i - 1][j];
					f[i][j] = min(f[i][j], b + 1);
				}
				h[i][1][0] += f[i][j];
				h[i][1][0] = min(h[i][1][0], b + 1);
			}
			if(i & 1) {
				rep(k, j, i - 1) {
					g[i][j] += g[i - 1][k];
					g[i][j] = min(g[i][j], b + 1);
				}
				h[i][0][0] += g[i][j];
				h[i][0][0] = min(h[i][0][0], b + 1);
			}
			else {
				rep(k, 1, i - 1) {
					g[i][j] += g[i - 1][j];
					g[i][j] = min(g[i][j], b + 1);
				}
				h[i][0][1] += g[i][j];
				h[i][0][1] = min(h[i][0][1], b + 1);
			}
			// f[i][j] = i & 1 ? f[i - 1][< j] : f[i - 1][>= j];
			// g[i][j] = i & 1 ? g[i - 1][>= j] : f[i - 1][< j];
		}
	}
	// s[a] = 1;
	// cout << calc() << endl;
	// return 0;
	// cout << h[2][0][1] << endl;
	rep(i, 1, a) {
		bool is = 0;
		rep(j, 1, a) if(!s[j]) {
			s[j] = 1;
			int tmp = calc();
			// cout << i << ' ' << tmp << endl;
			// rep(k, 1, a) cout << s[k] << " \n"[k == a];
			if(b <= tmp) {
				ans[i] = j;
				is = 1;
				break;
			}
			else {
				b -= tmp;
				s[j] = 0;
			}
		}
		if(!is) return cout << -1, 0;
	}
	rep(i, 1, a) cout << ans[i] << ' ';
	return 0;
}

详细

Test #1:

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

input:

3 2

output:

2 1 3 

result:

ok 3 number(s): "2 1 3"

Test #2:

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

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

4 6

output:

3 1 2 4 

result:

ok 4 number(s): "3 1 2 4"

Test #4:

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

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3684kb

input:

3 1

output:

1 2 3 

result:

wrong answer 2nd numbers differ - expected: '3', found: '2'