QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #125904 | #6319. Parallel Processing (Easy) | Energy_is_not_over | AC ✓ | 1ms | 3516kb | C++17 | 9.3kb | 2023-07-17 21:36:44 | 2023-07-17 21:36:46 |
Judging History
answer
/**
* created: 17/07/2023, 13:18:00
**/
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define all(a) a.begin(),a.end()
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
const int max_n = 16, inf = 1000111222;
const int magic = 500111222;
const int max_states = 50000;
long long coef[max_n];
int get_digit(long long mask, int pos) {
return (mask / coef[pos]) % (pos + 1);
}
void normalize(vector<pair<long long, long long>> &v, int magic) {
if (v.size() >= magic) {
cout << "normalize: " << v.size() << " -> ";
cout.flush();
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end(), [](const pair<long long, long long> &a, const pair<long long, long long> &b) {
return a.first == b.first;
}), v.end());
cout << v.size() << endl;
}
}
int func(long long mask) {
int res = 0;
for (int i = max_n - 1; i >= 0; --i) {
res += get_digit(mask, i);
}
return res;
}
vector<pair<long long, long long>> dist1[7];
vector<pair<long long, long long>> ans(max_n + 1, {-1, -1});
long long pans[max_n + 1];
void add(long long to, long long parent, int len) {
for (int i = 0; i < max_n; ++i) {
if (get_digit(to, i) != 0) {
break;
}
if (ans[i + 1].first == -1) {
ans[i + 1] = {to, len};
pans[i + 1] = parent;
cout << "ans: " << i + 1 << " " << len << endl;
}
}
dist1[len].push_back({to, parent});
}
int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
if (1) {
int N;
cin >> N;
stringstream ss("1 2 1 2 3 2 3 4 3 4 5 4 5 2 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 5 3 5 6 5 6 2 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 5 3 5 6 5 6 3 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 5 3 5 6 5 6 5 1 5 6 3 6 7 6 7 8 7 8 3 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 5 3 5 6 5 6 5 1 5 6 3 6 7 6 7 8 7 8 3 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 5 4 5 7 6 7 5 2 5 6 4 6 7 4 7 8 6 8 3 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 7 6 7 8 6 8 5 4 5 6 4 6 7 4 7 8 4 8 4 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 7 6 7 8 6 8 5 4 5 6 4 6 7 4 7 8 4 8 9 8 9 10 9 10 11 10 11 12 11 12 4 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 6 4 6 7 4 7 8 7 8 8 4 8 9 7 9 10 7 10 11 10 11 4 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 6 4 6 7 4 7 11 10 11 8 7 8 9 7 9 10 7 10 11 7 11 5 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 6 4 6 7 4 7 11 10 11 8 7 8 9 7 9 10 7 10 11 7 11 12 11 12 13 12 13 14 13 14 15 14 15 5 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 6 4 6 7 4 7 12 11 12 8 7 8 9 7 9 10 7 10 13 12 13 11 10 11 12 10 12 13 10 13 14 13 14 6 2 1 2 4 3 4 6 5 6 11 10 11 3 2 3 4 2 4 8 7 8 12 11 12 5 4 5 6 4 6 9 8 9 13 12 13 7 6 7 8 6 8 9 6 9 14 13 14 10 9 10 11 9 11 12 9 12 13 9 13 14 9 14 15 14 15 16 15 16 47 47 47 6 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 6 4 6 7 4 7 12 11 12 8 7 8 9 7 9 10 7 10 13 12 13 11 10 11 12 10 12 13 10 13 15 14 15 14 13 14 15 13 15 16 15 16 47 47 47 6 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 7 4 7 11 10 11 14 13 14 8 7 8 9 7 9 11 7 11 15 14 15 6 4 6 10 7 10 12 11 12 16 15 16 13 12 13 14 12 14 15 12 15 16 12 16");
for (int n = 2; n <= N; ++n) {
int k;
ss >> k;
if (n == N) {
cout << k << "\n";
}
for (int i = 0; i < 4 * k; ++i) {
for (int j = 0; j < 3; ++j) {
int x;
ss >> x;
if (n == N) {
cout << x << " ";
}
}
if (n == N) {
cout << "\n";
}
}
}
return 0;
}
coef[max_n - 1] = 1;
for (int i = max_n - 2; i >= 0; --i) {
coef[i] = coef[i + 1] * (i + 2);
}
add(coef[0] - 1, 0, 0);
for (int it = 0; it < 6; ++it) {
for (auto [cur, parent] : dist1[it]) {
vector<int> v(4);
for (v[0] = 1; v[0] < max_n; ++v[0]) {
if (!get_digit(cur, v[0])) {
continue;
}
for (v[1] = v[0] + 1; v[1] <= max_n; ++v[1]) {
if (v[1] < max_n && !get_digit(cur, v[1])) {
continue;
}
for (v[2] = min(max_n, v[1] + 1); v[2] <= max_n; ++v[2]) {
if (v[2] < max_n && !get_digit(cur, v[2])) {
continue;
}
for (v[3] = min(max_n, v[2] + 1); v[3] <= max_n; ++v[3]) {
if (v[3] < max_n && !get_digit(cur, v[3])) {
continue;
}
long long to = cur;
for (int i = 0; i < 4; ++i) {
if (v[i] == max_n) {
continue;
}
const int old = get_digit(cur, v[i]);
if (old) {
to -= old * coef[v[i]];
to += get_digit(cur, old - 1) * coef[v[i]];
}
}
add(to, cur, it + 1);
}
}
}
}
normalize(dist1[it + 1], magic);
}
normalize(dist1[it + 1], 0);
vector<pair<int, pair<long long, long long>>> v;
for (auto x : dist1[it + 1]) {
v.push_back({func(x.first), x});
}
sort(v.begin(), v.end());
v.resize(min<int>(v.size(), max_states));
dist1[it + 1].clear();
for (auto [val, x] : v) {
dist1[it + 1].push_back(x);
}
for (int i = 0; i <= max_n; ++i) {
if (ans[i].second == it + 1) {
dist1[it + 1].push_back({ans[i].first, pans[i]});
}
}
normalize(dist1[it + 1], 0);
cout << it << ": " << dist1[it + 1].size() << endl;
}
stringstream ss;
for (int n = 2; n <= 16; ++n) {
if (ans[n].first == -1) {
continue;
}
long long cur = ans[n].first;
cout << "#" << n << " " << cur << " " << ans[n].second << endl;
vector<string> ops;
for (int I = ans[n].second; I; --I) {
auto it = lower_bound(dist1[I].begin(), dist1[I].end(), make_pair(cur, -1LL));
assert(it != dist1[I].end() && it->first == cur);
long long parent = it->second;
long long nxt = cur;
cur = parent;
vector<int> v(4);
for (v[0] = 1; v[0] < max_n; ++v[0]) {
if (!get_digit(cur, v[0])) {
continue;
}
for (v[1] = v[0] + 1; v[1] <= max_n; ++v[1]) {
if (v[1] < max_n && !get_digit(cur, v[1])) {
continue;
}
for (v[2] = min(max_n, v[1] + 1); v[2] <= max_n; ++v[2]) {
if (v[2] < max_n && !get_digit(cur, v[2])) {
continue;
}
for (v[3] = min(max_n, v[2] + 1); v[3] <= max_n; ++v[3]) {
if (v[3] < max_n && !get_digit(cur, v[3])) {
continue;
}
long long to = cur;
for (int i = 0; i < 4; ++i) {
if (v[i] == max_n) {
continue;
}
const int old = get_digit(cur, v[i]);
if (old) {
to -= old * coef[v[i]];
to += get_digit(cur, old - 1) * coef[v[i]];
}
}
if (to == nxt) {
stringstream op;
for (int i = 0; i < 4; ++i) {
if (v[i] == max_n) {
op << "47 47 47 ";
} else {
op << v[i] + 1 << " " << get_digit(cur, v[i]) << " " << v[i] + 1 << " ";
}
}
ops.push_back(op.str());
}
}
}
}
}
}
assert(cur == coef[0] - 1);
reverse(ops.begin(), ops.end());
ss << ops.size() << " ";
for (string s : ops) {
ss << s;
}
}
cout << ss.str() << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3464kb
input:
2
output:
1 2 1 2 3 2 3 4 3 4 5 4 5
result:
ok AC
Test #2:
score: 0
Accepted
time: 1ms
memory: 3412kb
input:
4
output:
2 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 5 3 5 6 5 6
result:
ok AC
Test #3:
score: 0
Accepted
time: 1ms
memory: 3440kb
input:
3
output:
2 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 5 3 5 6 5 6
result:
ok AC
Test #4:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
5
output:
3 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 5 3 5 6 5 6 5 1 5 6 3 6 7 6 7 8 7 8
result:
ok AC
Test #5:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
6
output:
3 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 5 3 5 6 5 6 5 1 5 6 3 6 7 6 7 8 7 8
result:
ok AC
Test #6:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
7
output:
3 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 5 4 5 7 6 7 5 2 5 6 4 6 7 4 7 8 6 8
result:
ok AC
Test #7:
score: 0
Accepted
time: 1ms
memory: 3448kb
input:
8
output:
3 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 7 6 7 8 6 8 5 4 5 6 4 6 7 4 7 8 4 8
result:
ok AC
Test #8:
score: 0
Accepted
time: 1ms
memory: 3448kb
input:
9
output:
4 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 7 6 7 8 6 8 5 4 5 6 4 6 7 4 7 8 4 8 9 8 9 10 9 10 11 10 11 12 11 12
result:
ok AC
Test #9:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
10
output:
4 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 6 4 6 7 4 7 8 7 8 8 4 8 9 7 9 10 7 10 11 10 11
result:
ok AC
Test #10:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
11
output:
4 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 6 4 6 7 4 7 11 10 11 8 7 8 9 7 9 10 7 10 11 7 11
result:
ok AC
Test #11:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
12
output:
5 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 6 4 6 7 4 7 11 10 11 8 7 8 9 7 9 10 7 10 11 7 11 12 11 12 13 12 13 14 13 14 15 14 15
result:
ok AC
Test #12:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
13
output:
5 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 6 4 6 7 4 7 12 11 12 8 7 8 9 7 9 10 7 10 13 12 13 11 10 11 12 10 12 13 10 13 14 13 14
result:
ok AC
Test #13:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
14
output:
6 2 1 2 4 3 4 6 5 6 11 10 11 3 2 3 4 2 4 8 7 8 12 11 12 5 4 5 6 4 6 9 8 9 13 12 13 7 6 7 8 6 8 9 6 9 14 13 14 10 9 10 11 9 11 12 9 12 13 9 13 14 9 14 15 14 15 16 15 16 47 47 47
result:
ok AC
Test #14:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
15
output:
6 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 6 4 6 7 4 7 12 11 12 8 7 8 9 7 9 10 7 10 13 12 13 11 10 11 12 10 12 13 10 13 15 14 15 14 13 14 15 13 15 16 15 16 47 47 47
result:
ok AC
Test #15:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
16
output:
6 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 7 4 7 11 10 11 14 13 14 8 7 8 9 7 9 11 7 11 15 14 15 6 4 6 10 7 10 12 11 12 16 15 16 13 12 13 14 12 14 15 12 15 16 12 16
result:
ok AC