oj.uz

Submission #391081

# Submission time Handle Problem Language Result Execution time Memory
391081 2021-04-17T19:30:31 Z kostia244 Swap (BOI16_swap) C++17
100 / 100
 559 ms 8920 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;
}
bool cmp(const int &x, const stri &y, const stri &z, const int &a, const stri &b, const stri &c) {
	if(x != a) return x < a;
	for(int i = 0, j = 0, len = 1; i < y.size() || j < z.size(); len*=2) {
		for(int T = min((int)y.size(), i+len); i < T; i++)
			if(y[i] != b[i]) return y[i] < b[i];
		for(int T = min((int)z.size(), j+len); j < T; j++)
			if(z[j] != c[j]) return z[j] < c[j];
	}
	return 0;
}
int sum = 0;
vector<stri> solve(int l, int r, vector<int> vals) {
	if(l >= r) exit(1);
	if(l+1 == r) {
		sum++;
		vector<stri> ans;
		for(auto i : vals) ans.push_back(stri{i});
		return ans;
	}
	if(l+2 == r) {
		sum++;
		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++) {
		bool A = cmp(vals[i], L.back(), R.back(), a[l+1], L[i], R.back());
		bool B = cmp(a[x], L.back(), R[i], a[x], L[i], R[R.size()-2]);
		bool C = cmp(A ? vals[i] : a[l+1], A ? L.back() : L[i], R.back(),
					 a[x], B ? L.back() : L[i], B ? R[i] : R[R.size()-2]);
		if(C) {
			if(A)
				ans[i] = stri{vals[i]} + mer(L.back(), R.back());
			else
				ans[i] = stri{a[l+1]} + mer(L[i], R.back());
		} else {
			if(B)
				ans[i] = stri{a[x]} + mer(L.back(), R[i]);
			else
				ans[i] = stri{a[x]} + mer(L[i], R[R.size()-2]);
		}
		sum+=ans[i].size();
	}
	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';
	//cerr << sum << '\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 'bool cmp(const int&, const stri&, const stri&, const int&, const stri&, const stri&)':
swap.cpp:24:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i = 0, j = 0, len = 1; i < y.size() || j < z.size(); len*=2) {
      |                                 ~~^~~~~~~~~~
swap.cpp:24:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i = 0, j = 0, len = 1; i < y.size() || j < z.size(); len*=2) {
      |                                                 ~~^~~~~~~~~~
swap.cpp: In function 'std::vector<std::__cxx11::basic_string<int> > solve(int, int, std::vector<int>)':
swap.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i = 0; i < vals.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:95:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   95 |  for(auto i : X) cout << i << " "; cout << '\n';
      |  ^~~
swap.cpp:95:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   95 |  for(auto i : X) cout << i << " "; cout << '\n';
      |                                    ^~~~

Subtask #1
10.0 / 10.0

# 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

Subtask #2
11.0 / 11.0

# 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 332 KB Output is correct
10 Correct 1 ms 320 KB Output is correct

Subtask #3
27.0 / 27.0

# 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 332 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct

Subtask #4
20.0 / 20.0

# 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 332 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 110 ms 2616 KB Output is correct
17 Correct 109 ms 2556 KB Output is correct
18 Correct 108 ms 2500 KB Output is correct
19 Correct 116 ms 2580 KB Output is correct
20 Correct 110 ms 2588 KB Output is correct

Subtask #5
32.0 / 32.0

# 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 332 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 110 ms 2616 KB Output is correct
17 Correct 109 ms 2556 KB Output is correct
18 Correct 108 ms 2500 KB Output is correct
19 Correct 116 ms 2580 KB Output is correct
20 Correct 110 ms 2588 KB Output is correct
21 Correct 504 ms 7756 KB Output is correct
22 Correct 503 ms 8864 KB Output is correct
23 Correct 559 ms 8920 KB Output is correct
24 Correct 510 ms 8872 KB Output is correct
25 Correct 498 ms 8892 KB Output is correct