QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#603821#7778. Turning Permutationorz_zWA 1ms7912kbC++145.4kb2024-10-01 19:42:452024-10-01 19:42:46

Judging History

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

  • [2024-10-01 19:42:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7912kb
  • [2024-10-01 19:42:45]
  • 提交

answer

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize("Ofast,fast-math")
//#pragma GCC target("avx,avx2")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;
#define F(i, a, b) for(int i = a; i <= (b); ++i)
#define F2(i, a, b) for(int i = a; i < (b); ++i)
#define dF(i, a, b) for(int i = a; i >= (b); --i)
template<typename T> void debug(string s, T x) {
	cerr << "[" << s << "] = [" << x << "]\n";
}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {
	for (int i = 0, b = 0; i < (int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++;
	else if (s[i] == ')' || s[i] == '}') b--;
	else if (s[i] == ',' && b == 0) {
		cerr << "[" << s.substr(0, i) << "] = [" << x << "] | ";
		debug(s.substr(s.find_first_not_of(' ', i + 1)), args...);
		break;
	}
}
#ifdef ONLINE_JUDGE
#define Debug(...)
#else
#define Debug(...) debug(#__VA_ARGS__, __VA_ARGS__)
#endif
#define pb push_back
#define fi first
#define se second
#define Mry fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0)
#define Try cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
typedef long long ll;
// namespace Fread {const int SIZE = 1 << 17; char buf[SIZE], *S, *T; inline char getchar() {if (S == T) {T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n';} return *S++;}}
// namespace Fwrite {const int SIZE = 1 << 17; char buf[SIZE], *S = buf, *T = buf + SIZE; inline void flush() {fwrite(buf, 1, S - buf, stdout), S = buf;} inline void putchar(char c) {*S++ = c;if (S == T) flush();} struct NTR {~NTR() {flush();}} ztr;}
// #ifdef ONLINE_JUDGE
// #define getchar Fread::getchar
// #define putchar Fwrite::putchar
// #endif
inline int ri() {
	int x = 0;
	bool t = 0;
	char c = getchar();
	while (c < '0' || c > '9') t |= c == '-', c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return t ? -x : x;
}
inline void wi(int x) {
	if (x < 0) {
		putchar('-'), x = -x;
	}
	if (x > 9) wi(x / 10);
	putchar(x % 10 + 48);
}
inline void wi(int x, char s) {
	wi(x), putchar(s);
}
bool Mbe;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
const int _ = 2e5 + 5;

int n, k, a[_], b[_], tot[_];

bool flg[_], fg[_];

int qpow(int x, int y) {
	int res = 1;
	while(y) {
		if(y & 1) res = 1ll * res * x;
		x = 1ll * x *x , y>>= 1;
	} return res;
}

int f[105] = {0, 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, 707584, 5405530, 44736512, 398721962, 3807514624, 38783024290, 419730685952, 4809759350882, 58177770225664, 740742376475050, 9902996106248192, 138697748786275802, 2030847773013704704};
bool Med;
signed main() {
	// Mry;
//	Debug(LLONG_MAX);
//	Debug(infll);
//	Debug(f[24]);
	F(i, 25, 51) f[i] = infll;
	n = ri(), k = ri();
	__int128 sum = 0;
	F(z, 1, n) {
		bool fp = 0;
		__int128 lst = sum;
		F(j, 1, n) if(!flg[j]) {
			F(i, 1, n) b[i] = 0;
			F(i, 1, z - 1) b[a[i]] = i;
			b[j] = z;
			int Fg = 0;
			int jb = 1;
			F(i, 1, n - 1) if(b[i] && b[i + 1]) {
				if(!Fg) {
					if(b[i] < b[i + 1]) {
						Fg = i & 1;
						if(!Fg) Fg = 2;
						// Fg=1: 奇数<偶数>奇数
						// Fg=2:奇数>偶数<奇数数
					} else {
						Fg = ((i - 1) & 1);
						if(!Fg) Fg = 2;
					}
				} else {
					if(b[i] < b[i + 1]) {
						int w = i & 1;
						if(!w) w = 2;
						if(w != Fg) {
							jb = 0;
						}
					} else {
						int w = ((i - 1) & 1);
						if(!w) w = 2;
						if(w != Fg) {
							jb = 0;
						}
					}
				}
			}
			if(Fg && !jb) continue;
			F(i, 1, n - 1) if(b[i] && !b[i + 1]) {
				// 这意味着i<i+1
				if(Fg == 1) {
					if(i & 1);
					else {
						jb = 0;
					}
				} else {
					if(i % 2 == 0);
						else {
							jb = 0;
						}
				}
			} else if(!b[i] && b[i + 1]) {
				// 这意味着i>i+1
				if(Fg == 1) {
					if(i % 2 == 0);
					else jb = 0;
				} else {
					if(i & 1);
					else jb = 0;
				}
			}
			F(i, 1, n) b[i] = 0;
			a[z] = j;
			if(Fg && !jb) continue;
			auto chk = [&]() -> bool {
				F(i, 1, n) fg[i] = 0;
				F(i, 1, z) fg[a[i]] = 1;
				vector<pii> A;
				int res = 1;
				F(i, 1, n) tot[i] = 0;
				for(int i = 1; i <= n; ++i) if(!fg[i]) {
					int j = i + 1;
					while(j <= n && !fg[j]) j++;
					// [i, j - 1]
					int len = j - i;
					Debug(i, j - 1, len, f[len]);
					__int128 W = sum;
					W += (__int128)res * f[len];
					Debug((ll)W);
					if(W >= k) return 1;
					F(p, 1, len) tot[p]++;
					res = res * f[len];
					i = j - 1;
				}
				__int128 zkw = res;
				Debug((ll)zkw);
				F(i, 1, n - z) {
					zkw = zkw * i;
					F(j, 1, n) while(tot[j] && zkw % j == 0) {
						zkw /= j;
						tot[j]--;
					}
				}
				Debug(z, j, (ll)zkw);
				if(sum + zkw >= k) return 1;
				sum += zkw;
				return 0;
			};
			if(chk()) {
				Debug(z, j, (ll)sum);
				flg[j] = 1;
				a[z] = j;
				fp = 1;
				sum = lst;
				break;
			} else {
				lst = sum;
				continue;
			}
		}
			if(!fp) {
				puts("-1");
				return 0;
			}
	}
	F(i, 1, n) cout << a[i] << ' ';
	cout << '\n';
	// Try;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5836kb

input:

3 2

output:

2 1 3 

result:

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

Test #2:

score: 0
Accepted
time: 1ms
memory: 7912kb

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 7708kb

input:

4 6

output:

3 1 2 4 

result:

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

Test #4:

score: 0
Accepted
time: 1ms
memory: 5600kb

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 5836kb

input:

3 1

output:

1 3 2 

result:

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

Test #6:

score: 0
Accepted
time: 1ms
memory: 5600kb

input:

3 10

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

score: 0
Accepted
time: 1ms
memory: 7640kb

input:

3 52

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

score: 0
Accepted
time: 1ms
memory: 5632kb

input:

3 756

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 1ms
memory: 7700kb

input:

3 7721

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

score: 0
Accepted
time: 1ms
memory: 5548kb

input:

5 1

output:

1 3 2 5 4 

result:

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

Test #11:

score: -100
Wrong Answer
time: 1ms
memory: 5700kb

input:

5 8

output:

2 4 1 5 3 

result:

wrong answer 4th numbers differ - expected: '3', found: '5'