QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#407820#4252. Permutationzhaohaikun#0 81ms3988kbC++202.8kb2024-05-09 11:40:372024-05-09 11:40:39

Judging History

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

  • [2024-05-09 11:40:39]
  • 评测
  • 测评结果:0
  • 用时:81ms
  • 内存:3988kb
  • [2024-05-09 11:40:37]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#include "perm.h"
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\033[32m[" << __LINE__ << "]\033[0m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
mt19937 mrand(20070803);
const int T = 90;
inline int rnd(int l, int r) {return mrand() % (r - l + 1) + l;}
int cc(ll n) {
	if (n == 0) return 0;
	if (n % 2 == 1) return cc(n / 2) + 1;
	return cc(n - 1) + 1;
}
vector <int> solve(ll n) {
	if (n == 0) return vector <int> {};
	if (n % 2 == 1) {
		vector <int> ans = solve(n / 2);
		int t = ans.size();
		ans.push_back(t);
		return ans;
	}
	vector <int> ans = solve(n - 1);
	// int t = ans.size();
	for (int& i: ans) i++;
	ans.push_back(0);
	return ans;
}
// ll dp[1010];
ll t[1010];
int len;
void modify(int x, ll y) {
	for (; x <= len; x += x & -x) t[x] += y;
}
ll query(int x) {
	ll s = 0;
	for (; x; x ^= x & -x) s += t[x];
	return s;
}
ll calc(vector <int> x) {
	len = SZ(x);
	F(i, 1, len) t[i] = 0;
	ll s = 0;
	F(i, 0, SZ(x)) {
		ll w = 1 + query(x[i]);
		// F(j, 0, i - 1) {
		// 	if (x[j] < x[i]) {
		// 		dp[i] += dp[j];
		// 	}
		// }
		s += w;
		modify(x[i] + 1, w);
	}
	return s;
}
std::vector<int> construct_permutation(ll n) {
	n--;
	vector <int> ans;
	// if (n <= 90) {
	// 	F(i, 1, n) ans.push_back(n - i);
	// 	return ans;
	// }
	ans = solve(n);
	int lim = 1;
	F(i, 1, 7) {
		vector <int> t(i);
		F(j, 1, i) t[j - 1] = j - 1;
		// lim = min(500, lim * i);
		do {
		// F(j, 1, lim) {
			shuffle(all(t), mrand);
			ll v = calc(t);
			// debug << v << endl;
			if (n >= v) {
				// vector <int> w = cc(n - v);
				if (cc(n - v) + i < ans.size()) {
					assert(false);
					vector <int> w = solve(n - v);
					ans.clear();
					for (int j: t) ans.push_back(j + w.size());
					for (int j: w) ans.push_back(j);
					if (ans.size() <= T) break;
				}
			}
		// }
		} while (next_permutation(all(t)));
		// if (ans.size() <= T) break;
	}
	return ans;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

a92b3f80-b312-8377-273c-3916024d7f2a
89
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

output:

Unauthorized output

result:


Subtask #2:

score: 0
Runtime Error

Test #2:

score: 90
Accepted
time: 81ms
memory: 3988kb

input:

a92b3f80-b312-8377-273c-3916024d7f2a
100
39993
85709
48645
25391
15360
54084
28947
18808
86735
316
14357
82845
96210
16242
58466
43439
77462
70742
76176
20397
30314
22634
29622
81835
31904
81283
37072
36527
26764
55878
72762
5262
34915
63468
20595
66579
77373
36670
89340
83384
73268
31960
67318
3908...

output:

6cad0f33-b1bd-3a3e-1a8d-c4af23adfcbf
OK
22
7 8 9 6 10 5 11 4 12 13 14 15 16 3 17 2 18 1 19 20 21 0
25
9 10 8 11 12 13 7 14 6 15 5 16 17 4 18 3 19 20 21 2 22 1 23 24 0
22
7 8 6 9 5 10 4 11 3 12 2 13 14 15 16 17 18 19 1 20 21 0
22
8 7 9 10 11 12 6 13 5 14 15 16 4 17 18 3 19 2 20 1 21 0
16
3 2 4 1 5 0 ...

result:

ok 

Test #3:

score: 0
Runtime Error

input:

a92b3f80-b312-8377-273c-3916024d7f2a
100
2147483647
1073741823
536870911
268435455
134217727
67108863
33554431
16777215
8388607
4194303
2097151
1582
24319
38
463
7
1073741503
3
18
3
3780
2
24934
124910
65535
154
1069539071
209452285
1662
3
3
93
4070
131071
502986749
3164
268430159
247
21746
124927
1...

output:

Unauthorized output

result: