| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 224180 |
2020-04-17T11:23:00 Z |
Bruteforceman |
Swap (BOI16_swap) |
C++11 |
|
319 ms |
6376 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair <int, int>;
int dp[1005][1005];
int a[1005];
int op[1005][1005];
int n;
void dfs(int x) {
int l = x << 1;
int r = l + 1;
if(l <= n) dfs(l);
if(r <= n) dfs(r);
if(r <= n) {
for(int y = 1; y <= n; y++) {
vector <pii> opt ({{INT_MAX, INT_MAX}, {INT_MAX, INT_MAX}, {INT_MAX, INT_MAX}});
for(int i = 0; i <= 1; i++) {
for(int j = 0; j <= 1; j++) {
int p = y, q = a[l], s = a[r];
if(i) swap(p, q);
if(j) swap(p, s);
vector <pii> can;
can.emplace_back(x, p);
can.emplace_back(dp[l][q], q);
can.emplace_back(dp[r][s], s);
sort(can.begin(), can.end());
if(opt > can) {
opt = can;
for(auto w : can) if(w.second == y) dp[x][y] = w.first;
op[x][y] = j * 2 + i;
}
}
}
}
} else if (l <= n) {
for(int y = 1; y <= n; y++) {
vector <pii> opt ({{INT_MAX, INT_MAX}, {INT_MAX, INT_MAX}});
for(int i = 0; i <= 1; i++) {
int p = y, q = a[l];
if(i) swap(p, q);
vector <pii> can;
can.emplace_back(x, p);
can.emplace_back(dp[l][q], q);
sort(can.begin(), can.end());
if(opt > can) {
opt = can;
for(auto w : can) if(w.second == y) dp[x][y] = w.first;
op[x][y] = i;
}
}
}
} else {
for(int y = 1; y <= n; y++) {
dp[x][y] = x;
}
}
}
void getOpt(int x) {
int i = op[x][a[x]] & 1;
int j = op[x][a[x]] >> 1;
int l = x << 1;
int r = l + 1;
if(i) swap(a[x], a[l]);
if(j) swap(a[x], a[r]);
if(l <= n) getOpt(l);
if(r <= n) getOpt(r);
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
dfs(1);
getOpt(1);
for(int i = 1; i <= n; i++) {
cout << a[i] << ' ';
}
cout << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
512 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
640 KB |
Output is correct |
| 10 |
Correct |
5 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
512 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
640 KB |
Output is correct |
| 10 |
Correct |
5 ms |
512 KB |
Output is correct |
| 11 |
Correct |
305 ms |
6244 KB |
Output is correct |
| 12 |
Correct |
305 ms |
6376 KB |
Output is correct |
| 13 |
Correct |
307 ms |
6264 KB |
Output is correct |
| 14 |
Correct |
307 ms |
6136 KB |
Output is correct |
| 15 |
Correct |
319 ms |
6264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
512 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
640 KB |
Output is correct |
| 10 |
Correct |
5 ms |
512 KB |
Output is correct |
| 11 |
Correct |
305 ms |
6244 KB |
Output is correct |
| 12 |
Correct |
305 ms |
6376 KB |
Output is correct |
| 13 |
Correct |
307 ms |
6264 KB |
Output is correct |
| 14 |
Correct |
307 ms |
6136 KB |
Output is correct |
| 15 |
Correct |
319 ms |
6264 KB |
Output is correct |
| 16 |
Runtime error |
25 ms |
1144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
512 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
640 KB |
Output is correct |
| 10 |
Correct |
5 ms |
512 KB |
Output is correct |
| 11 |
Correct |
305 ms |
6244 KB |
Output is correct |
| 12 |
Correct |
305 ms |
6376 KB |
Output is correct |
| 13 |
Correct |
307 ms |
6264 KB |
Output is correct |
| 14 |
Correct |
307 ms |
6136 KB |
Output is correct |
| 15 |
Correct |
319 ms |
6264 KB |
Output is correct |
| 16 |
Runtime error |
25 ms |
1144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Halted |
0 ms |
0 KB |
- |
