| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 391072 |
2021-04-17T19:07:08 Z |
kostia244 |
Swap (BOI16_swap) |
C++17 |
|
1000 ms |
8652 KB |
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int maxn = 1<<18;
const ll inf = 1ll<<60;
int n, a[maxn], B[maxn], C[maxn];
using stri = basic_string<int>;
stri mer(stri a, stri b) {
stri res;
res.reserve(a.size()+b.size());
for(int i = 0, j = 0, len = 1; i < a.size() || j < b.size(); len*=2) {
for(int x = min((int)a.size(), i+len); i < x; i++)
res += a[i];
for(int y = min((int)b.size(), j+len); j < y; j++)
res += b[j];
}
return res;
}
vector<stri> solve(int l, int r, vector<int> vals) {
if(l >= r) exit(1);
if(l+1 == r) {
vector<stri> ans;
for(auto i : vals) ans.push_back(stri{i});
return ans;
}
if(l+2 == r) {
vector<stri> ans;
for(auto i : vals) {
ans.push_back({min(i, a[l+1]), max(i, a[l+1])});
}
return ans;
}
int x = C[l];
vals.push_back(a[l+1]);
auto L = solve(l+1, x, vals);
vals.push_back(a[x]);
auto R = solve(x, r, vals);
vals.pop_back(), vals.pop_back();
vector<stri> ans(vals.size());
//cout << a[l] << " " << a[l+1] << " " << a[x] << endl;
for(int i = 0; i < vals.size(); i++) {
ans[i] = stri{vals[i]} + mer(L.back(), R.back());
ans[i] = min(ans[i], stri{a[l+1]} + mer(L[i], R.back()));
ans[i] = min(ans[i], stri{a[x]} + mer(L.back(), R[i]));
ans[i] = min(ans[i], stri{a[x]} + mer(L[i], R[R.size()-2]));
}
return ans;
}
int S = 0;
void permute(int pos) {
if(pos > n) return;
int os = S;
a[S++] = B[pos-1];
permute(2*pos);
C[os] = S;
permute(2*pos+1);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 0; i < n; i++) cin >> B[i];
permute(1);
//for(int i = 0; i < n; i++) cout << a[i] << " "; cout << endl;
auto X = solve(0, n, {a[0]})[0];
for(auto i : X) cout << i << " "; cout << '\n';
}
Compilation message
swap.cpp: In function 'stri mer(stri, stri)':
swap.cpp:14:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int i = 0, j = 0, len = 1; i < a.size() || j < b.size(); len*=2) {
| ~~^~~~~~~~~~
swap.cpp:14:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int i = 0, j = 0, len = 1; i < a.size() || j < b.size(); len*=2) {
| ~~^~~~~~~~~~
swap.cpp: In function 'std::vector<std::__cxx11::basic_string<int> > solve(int, int, std::vector<int>)':
swap.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = 0; i < vals.size(); i++) {
| ~~^~~~~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:70:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
70 | for(auto i : X) cout << i << " "; cout << '\n';
| ^~~
swap.cpp:70:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
70 | for(auto i : X) cout << i << " "; cout << '\n';
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
4 ms |
336 KB |
Output is correct |
| 12 |
Correct |
4 ms |
332 KB |
Output is correct |
| 13 |
Correct |
4 ms |
332 KB |
Output is correct |
| 14 |
Correct |
4 ms |
388 KB |
Output is correct |
| 15 |
Correct |
4 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
4 ms |
336 KB |
Output is correct |
| 12 |
Correct |
4 ms |
332 KB |
Output is correct |
| 13 |
Correct |
4 ms |
332 KB |
Output is correct |
| 14 |
Correct |
4 ms |
388 KB |
Output is correct |
| 15 |
Correct |
4 ms |
332 KB |
Output is correct |
| 16 |
Correct |
290 ms |
2908 KB |
Output is correct |
| 17 |
Correct |
288 ms |
2908 KB |
Output is correct |
| 18 |
Correct |
289 ms |
2944 KB |
Output is correct |
| 19 |
Correct |
296 ms |
2972 KB |
Output is correct |
| 20 |
Correct |
293 ms |
2900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
4 ms |
336 KB |
Output is correct |
| 12 |
Correct |
4 ms |
332 KB |
Output is correct |
| 13 |
Correct |
4 ms |
332 KB |
Output is correct |
| 14 |
Correct |
4 ms |
388 KB |
Output is correct |
| 15 |
Correct |
4 ms |
332 KB |
Output is correct |
| 16 |
Correct |
290 ms |
2908 KB |
Output is correct |
| 17 |
Correct |
288 ms |
2908 KB |
Output is correct |
| 18 |
Correct |
289 ms |
2944 KB |
Output is correct |
| 19 |
Correct |
296 ms |
2972 KB |
Output is correct |
| 20 |
Correct |
293 ms |
2900 KB |
Output is correct |
| 21 |
Execution timed out |
1084 ms |
8652 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
