QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#603821 | #7778. Turning Permutation | orz_z | WA | 1ms | 7912kb | C++14 | 5.4kb | 2024-10-01 19:42:45 | 2024-10-01 19:42:46 |
Judging History
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'