답안 #76589 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
76589	2018-09-15T06:12:14 Z	tmwilliamlin168	Swap (BOI16_swap)	C++14	68 / 100	621 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];

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]) {
					vector<int> 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]);
	}
	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	160 ms	180344 KB	Output is correct
2	Correct	154 ms	180480 KB	Output is correct
3	Correct	158 ms	180640 KB	Output is correct
4	Correct	161 ms	180640 KB	Output is correct
5	Correct	162 ms	180640 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	160 ms	180344 KB	Output is correct
2	Correct	154 ms	180480 KB	Output is correct
3	Correct	158 ms	180640 KB	Output is correct
4	Correct	161 ms	180640 KB	Output is correct
5	Correct	162 ms	180640 KB	Output is correct
6	Correct	161 ms	180640 KB	Output is correct
7	Correct	157 ms	180856 KB	Output is correct
8	Correct	157 ms	180924 KB	Output is correct
9	Correct	157 ms	180924 KB	Output is correct
10	Correct	164 ms	180924 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	160 ms	180344 KB	Output is correct
2	Correct	154 ms	180480 KB	Output is correct
3	Correct	158 ms	180640 KB	Output is correct
4	Correct	161 ms	180640 KB	Output is correct
5	Correct	162 ms	180640 KB	Output is correct
6	Correct	161 ms	180640 KB	Output is correct
7	Correct	157 ms	180856 KB	Output is correct
8	Correct	157 ms	180924 KB	Output is correct
9	Correct	157 ms	180924 KB	Output is correct
10	Correct	164 ms	180924 KB	Output is correct
11	Correct	157 ms	181236 KB	Output is correct
12	Correct	157 ms	181236 KB	Output is correct
13	Correct	167 ms	181236 KB	Output is correct
14	Correct	166 ms	181456 KB	Output is correct
15	Correct	163 ms	181512 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	160 ms	180344 KB	Output is correct
2	Correct	154 ms	180480 KB	Output is correct
3	Correct	158 ms	180640 KB	Output is correct
4	Correct	161 ms	180640 KB	Output is correct
5	Correct	162 ms	180640 KB	Output is correct
6	Correct	161 ms	180640 KB	Output is correct
7	Correct	157 ms	180856 KB	Output is correct
8	Correct	157 ms	180924 KB	Output is correct
9	Correct	157 ms	180924 KB	Output is correct
10	Correct	164 ms	180924 KB	Output is correct
11	Correct	157 ms	181236 KB	Output is correct
12	Correct	157 ms	181236 KB	Output is correct
13	Correct	167 ms	181236 KB	Output is correct
14	Correct	166 ms	181456 KB	Output is correct
15	Correct	163 ms	181512 KB	Output is correct
16	Correct	236 ms	189332 KB	Output is correct
17	Correct	246 ms	189620 KB	Output is correct
18	Correct	231 ms	190048 KB	Output is correct
19	Correct	621 ms	223544 KB	Output is correct
20	Correct	615 ms	223544 KB	Output is correct

Subtask #5
0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	160 ms	180344 KB	Output is correct
2	Correct	154 ms	180480 KB	Output is correct
3	Correct	158 ms	180640 KB	Output is correct
4	Correct	161 ms	180640 KB	Output is correct
5	Correct	162 ms	180640 KB	Output is correct
6	Correct	161 ms	180640 KB	Output is correct
7	Correct	157 ms	180856 KB	Output is correct
8	Correct	157 ms	180924 KB	Output is correct
9	Correct	157 ms	180924 KB	Output is correct
10	Correct	164 ms	180924 KB	Output is correct
11	Correct	157 ms	181236 KB	Output is correct
12	Correct	157 ms	181236 KB	Output is correct
13	Correct	167 ms	181236 KB	Output is correct
14	Correct	166 ms	181456 KB	Output is correct
15	Correct	163 ms	181512 KB	Output is correct
16	Correct	236 ms	189332 KB	Output is correct
17	Correct	246 ms	189620 KB	Output is correct
18	Correct	231 ms	190048 KB	Output is correct
19	Correct	621 ms	223544 KB	Output is correct
20	Correct	615 ms	223544 KB	Output is correct
21	Correct	512 ms	223544 KB	Output is correct
22	Correct	483 ms	223544 KB	Output is correct
23	Correct	512 ms	223544 KB	Output is correct
24	Runtime error	495 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-

답안 #76589

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