답안 #76592 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
76592	2018-09-15T06:21:29 Z	tmwilliamlin168	Swap (BOI16_swap)	C++14	68 / 100	538 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+1];
vector<int> dp[mxN*18*2], v1, v2;

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]);
	}
}

void as(int i, int b) {
	if(di[i].find(b)==di[i].end())
		di[i][b]=cdi++;
}

vector<int>& gd(int i, int b) {
	return dp[di[i][b]];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i=1; i<=n; ++i)
		cin >> a[i];
	as(1, a[1]);
	for(int i=1; 2*i+1<=n; ++i) {
		for(auto it=di[i].begin(); it!=di[i].end(); ++it) {
			int b=it->first;
			if(a[2*i+1]<b&&a[2*i+1]<a[2*i]) {
				as(2*i, a[2*i]);
				as(2*i+1, b);
				as(2*i, b);
				as(2*i+1, a[2*i]);
			} else {
				as(2*i, max(b, a[2*i]));
				as(2*i+1, a[2*i+1]);
			}
		}
	}
	for(int i=n; i; --i) {
		for(auto it=di[i].begin(); it!=di[i].end(); ++it) {
			int b=it->first, c=it->second;
			if(2*i+1<=n) {
				if(a[2*i+1]<b&&a[2*i+1]<a[2*i]) {
					v1={a[2*i+1]};
					v2={a[2*i+1]};
					mrg(v1, gd(2*i, a[2*i]), gd(2*i+1, b));
					mrg(v2, gd(2*i, b), gd(2*i+1, a[2*i]));
					dp[c]=min(v1, v2);
				} else {
					dp[c]={min(b, a[2*i])};
					mrg(dp[c], gd(2*i, max(b, a[2*i])), gd(2*i+1, a[2*i+1]));
				}
			} else if(2*i<=n)
				dp[c]={min(b, a[2*i]), max(b, a[2*i])};
			else
				dp[c]={b};
		}
		if(2*i+1<=n) {
			for(int j=0; j<2; ++j) {
				for(auto it=di[2*i+j].begin(); it!=di[2*i+j].end(); ++it)
					vector<int>().swap(dp[it->second]);
				di[2*i+j].clear();
			}
		}
	}
	for(int b : dp[0])
		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	164 ms	180472 KB	Output is correct
2	Correct	163 ms	180648 KB	Output is correct
3	Correct	158 ms	180648 KB	Output is correct
4	Correct	165 ms	180788 KB	Output is correct
5	Correct	164 ms	180788 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	164 ms	180472 KB	Output is correct
2	Correct	163 ms	180648 KB	Output is correct
3	Correct	158 ms	180648 KB	Output is correct
4	Correct	165 ms	180788 KB	Output is correct
5	Correct	164 ms	180788 KB	Output is correct
6	Correct	158 ms	180788 KB	Output is correct
7	Correct	161 ms	180788 KB	Output is correct
8	Correct	171 ms	180812 KB	Output is correct
9	Correct	161 ms	181024 KB	Output is correct
10	Correct	165 ms	181024 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	164 ms	180472 KB	Output is correct
2	Correct	163 ms	180648 KB	Output is correct
3	Correct	158 ms	180648 KB	Output is correct
4	Correct	165 ms	180788 KB	Output is correct
5	Correct	164 ms	180788 KB	Output is correct
6	Correct	158 ms	180788 KB	Output is correct
7	Correct	161 ms	180788 KB	Output is correct
8	Correct	171 ms	180812 KB	Output is correct
9	Correct	161 ms	181024 KB	Output is correct
10	Correct	165 ms	181024 KB	Output is correct
11	Correct	160 ms	181024 KB	Output is correct
12	Correct	166 ms	181076 KB	Output is correct
13	Correct	166 ms	181104 KB	Output is correct
14	Correct	179 ms	181616 KB	Output is correct
15	Correct	164 ms	181616 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	164 ms	180472 KB	Output is correct
2	Correct	163 ms	180648 KB	Output is correct
3	Correct	158 ms	180648 KB	Output is correct
4	Correct	165 ms	180788 KB	Output is correct
5	Correct	164 ms	180788 KB	Output is correct
6	Correct	158 ms	180788 KB	Output is correct
7	Correct	161 ms	180788 KB	Output is correct
8	Correct	171 ms	180812 KB	Output is correct
9	Correct	161 ms	181024 KB	Output is correct
10	Correct	165 ms	181024 KB	Output is correct
11	Correct	160 ms	181024 KB	Output is correct
12	Correct	166 ms	181076 KB	Output is correct
13	Correct	166 ms	181104 KB	Output is correct
14	Correct	179 ms	181616 KB	Output is correct
15	Correct	164 ms	181616 KB	Output is correct
16	Correct	243 ms	189316 KB	Output is correct
17	Correct	230 ms	189684 KB	Output is correct
18	Correct	239 ms	190048 KB	Output is correct
19	Correct	506 ms	223484 KB	Output is correct
20	Correct	494 ms	223528 KB	Output is correct

Subtask #5
0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	164 ms	180472 KB	Output is correct
2	Correct	163 ms	180648 KB	Output is correct
3	Correct	158 ms	180648 KB	Output is correct
4	Correct	165 ms	180788 KB	Output is correct
5	Correct	164 ms	180788 KB	Output is correct
6	Correct	158 ms	180788 KB	Output is correct
7	Correct	161 ms	180788 KB	Output is correct
8	Correct	171 ms	180812 KB	Output is correct
9	Correct	161 ms	181024 KB	Output is correct
10	Correct	165 ms	181024 KB	Output is correct
11	Correct	160 ms	181024 KB	Output is correct
12	Correct	166 ms	181076 KB	Output is correct
13	Correct	166 ms	181104 KB	Output is correct
14	Correct	179 ms	181616 KB	Output is correct
15	Correct	164 ms	181616 KB	Output is correct
16	Correct	243 ms	189316 KB	Output is correct
17	Correct	230 ms	189684 KB	Output is correct
18	Correct	239 ms	190048 KB	Output is correct
19	Correct	506 ms	223484 KB	Output is correct
20	Correct	494 ms	223528 KB	Output is correct
21	Correct	489 ms	223528 KB	Output is correct
22	Correct	530 ms	223528 KB	Output is correct
23	Correct	526 ms	223528 KB	Output is correct
24	Runtime error	538 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-

답안 #76592

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