답안 #76584 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
76584	2018-09-15T05:20:13 Z	tmwilliamlin168	Swap (BOI16_swap)	C++14	68 / 100	790 ms	263168 KB

swap

#include <bits/stdc++.h>
using namespace std;

const int mxN=2e5;
int n, a[mxN+1], cdi;
unordered_map<int, int> di[mxN];
vector<int> dp[mxN*18*2];

void mrg(vector<int> &v, vector<int> &a, vector<int> &b) {
	for(int l=1, i=0, j=0; i<a.size()||j<b.size(); i+=l, j+=l, l*=2) {
		for(int k=0; k<l&&i+k<a.size(); ++k)
			v.push_back(a[i+k]);
		for(int k=0; k<l&&j+k<b.size(); ++k)
			v.push_back(b[j+k]);
	}
}

int c(int i, int b) {
	auto it=di[i].find(b);
	if(it!=di[i].end())
		return it->second;
	int r=cdi++;
	di[i][b]=r;
	if(2*i+1<=n) {
		if(a[2*i+1]<b&&a[2*i+1]<a[2*i]) {
			vector<int> v1={a[2*i+1]}, v2={a[2*i+1]};
			mrg(v1, dp[c(2*i, a[2*i])], dp[c(2*i+1, b)]);
			mrg(v2, dp[c(2*i, b)], dp[c(2*i+1, a[2*i])]);
//			if(i==1&&b==3) {
//				cout << "hi1" << endl;
//				cout << a[2*i] << " " << b << endl;
//				for(int j=0; j<v1.size(); ++j)
//					cout << v1[j] << " ";
//				cout << endl;
//				cout << b << " " << a[2*i] << endl;
//				for(int j=0; j<v2.size(); ++j)
//					cout << v2[j] << " ";
//				cout << endl;
//			}
			dp[r]=min(v1, v2);
		} else {
			dp[r]={min(b, a[2*i])};
			mrg(dp[r], dp[c(2*i, max(b, a[2*i]))], dp[c(2*i+1, a[2*i+1])]);
		}
	} else if(2*i<=n)
		dp[r]={min(b, a[2*i]), max(b, a[2*i])};
	else
		dp[r]={b};
//	cout << i << " " << b << endl;
//	for(int j=0; j<dp[r].size(); ++j)
//		cout << dp[r][j] << " ";
//	cout << "a" << endl;
	return r;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i=1; i<=n; ++i)
		cin >> a[i];
	for(int b : dp[c(1, a[1])])
		cout << b << " ";
}

Compilation message

swap.cpp: In function 'void mrg(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:10:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int l=1, i=0, j=0; i<a.size()||j<b.size(); i+=l, j+=l, l*=2) {
                         ~^~~~~~~~~
swap.cpp:10:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int l=1, i=0, j=0; i<a.size()||j<b.size(); i+=l, j+=l, l*=2) {
                                     ~^~~~~~~~~
swap.cpp:11:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0; k<l&&i+k<a.size(); ++k)
                     ~~~^~~~~~~~~
swap.cpp:13:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0; k<l&&j+k<b.size(); ++k)
                     ~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	158 ms	180344 KB	Output is correct
2	Correct	160 ms	180488 KB	Output is correct
3	Correct	158 ms	180508 KB	Output is correct
4	Correct	162 ms	180664 KB	Output is correct
5	Correct	160 ms	180700 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	158 ms	180344 KB	Output is correct
2	Correct	160 ms	180488 KB	Output is correct
3	Correct	158 ms	180508 KB	Output is correct
4	Correct	162 ms	180664 KB	Output is correct
5	Correct	160 ms	180700 KB	Output is correct
6	Correct	158 ms	180736 KB	Output is correct
7	Correct	171 ms	180868 KB	Output is correct
8	Correct	161 ms	180956 KB	Output is correct
9	Correct	162 ms	180956 KB	Output is correct
10	Correct	168 ms	180964 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	158 ms	180344 KB	Output is correct
2	Correct	160 ms	180488 KB	Output is correct
3	Correct	158 ms	180508 KB	Output is correct
4	Correct	162 ms	180664 KB	Output is correct
5	Correct	160 ms	180700 KB	Output is correct
6	Correct	158 ms	180736 KB	Output is correct
7	Correct	171 ms	180868 KB	Output is correct
8	Correct	161 ms	180956 KB	Output is correct
9	Correct	162 ms	180956 KB	Output is correct
10	Correct	168 ms	180964 KB	Output is correct
11	Correct	178 ms	181160 KB	Output is correct
12	Correct	161 ms	181420 KB	Output is correct
13	Correct	163 ms	181420 KB	Output is correct
14	Correct	166 ms	181768 KB	Output is correct
15	Correct	165 ms	181876 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	158 ms	180344 KB	Output is correct
2	Correct	160 ms	180488 KB	Output is correct
3	Correct	158 ms	180508 KB	Output is correct
4	Correct	162 ms	180664 KB	Output is correct
5	Correct	160 ms	180700 KB	Output is correct
6	Correct	158 ms	180736 KB	Output is correct
7	Correct	171 ms	180868 KB	Output is correct
8	Correct	161 ms	180956 KB	Output is correct
9	Correct	162 ms	180956 KB	Output is correct
10	Correct	168 ms	180964 KB	Output is correct
11	Correct	178 ms	181160 KB	Output is correct
12	Correct	161 ms	181420 KB	Output is correct
13	Correct	163 ms	181420 KB	Output is correct
14	Correct	166 ms	181768 KB	Output is correct
15	Correct	165 ms	181876 KB	Output is correct
16	Correct	245 ms	196400 KB	Output is correct
17	Correct	241 ms	196400 KB	Output is correct
18	Correct	250 ms	196936 KB	Output is correct
19	Correct	775 ms	252332 KB	Output is correct
20	Correct	790 ms	252332 KB	Output is correct

Subtask #5
0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	158 ms	180344 KB	Output is correct
2	Correct	160 ms	180488 KB	Output is correct
3	Correct	158 ms	180508 KB	Output is correct
4	Correct	162 ms	180664 KB	Output is correct
5	Correct	160 ms	180700 KB	Output is correct
6	Correct	158 ms	180736 KB	Output is correct
7	Correct	171 ms	180868 KB	Output is correct
8	Correct	161 ms	180956 KB	Output is correct
9	Correct	162 ms	180956 KB	Output is correct
10	Correct	168 ms	180964 KB	Output is correct
11	Correct	178 ms	181160 KB	Output is correct
12	Correct	161 ms	181420 KB	Output is correct
13	Correct	163 ms	181420 KB	Output is correct
14	Correct	166 ms	181768 KB	Output is correct
15	Correct	165 ms	181876 KB	Output is correct
16	Correct	245 ms	196400 KB	Output is correct
17	Correct	241 ms	196400 KB	Output is correct
18	Correct	250 ms	196936 KB	Output is correct
19	Correct	775 ms	252332 KB	Output is correct
20	Correct	790 ms	252332 KB	Output is correct
21	Correct	569 ms	252332 KB	Output is correct
22	Correct	574 ms	252332 KB	Output is correct
23	Correct	580 ms	252332 KB	Output is correct
24	Runtime error	715 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-

답안 #76584

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 11.0 / 11.0

Subtask #3 27.0 / 27.0

Subtask #4 20.0 / 20.0

Subtask #5 0 / 32.0

Subtask #1
10.0 / 10.0

Subtask #2
11.0 / 11.0

Subtask #3
27.0 / 27.0

Subtask #4
20.0 / 20.0

Subtask #5
0 / 32.0