답안 #76586 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
76586	2018-09-15T05:24:47 Z	tmwilliamlin168	Swap (BOI16_swap)	C++14	68 / 100	771 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])]);
			dp[r]=min(v1, v2);
			vector<int>().swap(v1);
			vector<int>().swap(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};
	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	156 ms	180344 KB	Output is correct
2	Correct	155 ms	180488 KB	Output is correct
3	Correct	154 ms	180548 KB	Output is correct
4	Correct	163 ms	180720 KB	Output is correct
5	Correct	155 ms	180900 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	156 ms	180344 KB	Output is correct
2	Correct	155 ms	180488 KB	Output is correct
3	Correct	154 ms	180548 KB	Output is correct
4	Correct	163 ms	180720 KB	Output is correct
5	Correct	155 ms	180900 KB	Output is correct
6	Correct	167 ms	180900 KB	Output is correct
7	Correct	152 ms	180900 KB	Output is correct
8	Correct	166 ms	180900 KB	Output is correct
9	Correct	155 ms	180900 KB	Output is correct
10	Correct	164 ms	180900 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	156 ms	180344 KB	Output is correct
2	Correct	155 ms	180488 KB	Output is correct
3	Correct	154 ms	180548 KB	Output is correct
4	Correct	163 ms	180720 KB	Output is correct
5	Correct	155 ms	180900 KB	Output is correct
6	Correct	167 ms	180900 KB	Output is correct
7	Correct	152 ms	180900 KB	Output is correct
8	Correct	166 ms	180900 KB	Output is correct
9	Correct	155 ms	180900 KB	Output is correct
10	Correct	164 ms	180900 KB	Output is correct
11	Correct	160 ms	181068 KB	Output is correct
12	Correct	166 ms	181116 KB	Output is correct
13	Correct	168 ms	181196 KB	Output is correct
14	Correct	167 ms	181592 KB	Output is correct
15	Correct	170 ms	181600 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	156 ms	180344 KB	Output is correct
2	Correct	155 ms	180488 KB	Output is correct
3	Correct	154 ms	180548 KB	Output is correct
4	Correct	163 ms	180720 KB	Output is correct
5	Correct	155 ms	180900 KB	Output is correct
6	Correct	167 ms	180900 KB	Output is correct
7	Correct	152 ms	180900 KB	Output is correct
8	Correct	166 ms	180900 KB	Output is correct
9	Correct	155 ms	180900 KB	Output is correct
10	Correct	164 ms	180900 KB	Output is correct
11	Correct	160 ms	181068 KB	Output is correct
12	Correct	166 ms	181116 KB	Output is correct
13	Correct	168 ms	181196 KB	Output is correct
14	Correct	167 ms	181592 KB	Output is correct
15	Correct	170 ms	181600 KB	Output is correct
16	Correct	247 ms	196212 KB	Output is correct
17	Correct	255 ms	196212 KB	Output is correct
18	Correct	248 ms	196924 KB	Output is correct
19	Correct	771 ms	252280 KB	Output is correct
20	Correct	741 ms	252280 KB	Output is correct

Subtask #5
0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	156 ms	180344 KB	Output is correct
2	Correct	155 ms	180488 KB	Output is correct
3	Correct	154 ms	180548 KB	Output is correct
4	Correct	163 ms	180720 KB	Output is correct
5	Correct	155 ms	180900 KB	Output is correct
6	Correct	167 ms	180900 KB	Output is correct
7	Correct	152 ms	180900 KB	Output is correct
8	Correct	166 ms	180900 KB	Output is correct
9	Correct	155 ms	180900 KB	Output is correct
10	Correct	164 ms	180900 KB	Output is correct
11	Correct	160 ms	181068 KB	Output is correct
12	Correct	166 ms	181116 KB	Output is correct
13	Correct	168 ms	181196 KB	Output is correct
14	Correct	167 ms	181592 KB	Output is correct
15	Correct	170 ms	181600 KB	Output is correct
16	Correct	247 ms	196212 KB	Output is correct
17	Correct	255 ms	196212 KB	Output is correct
18	Correct	248 ms	196924 KB	Output is correct
19	Correct	771 ms	252280 KB	Output is correct
20	Correct	741 ms	252280 KB	Output is correct
21	Correct	551 ms	252280 KB	Output is correct
22	Correct	525 ms	252280 KB	Output is correct
23	Correct	555 ms	252280 KB	Output is correct
24	Runtime error	689 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-

답안 #76586

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