답안 #76600 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
76600	2018-09-15T06:31:56 Z	tmwilliamlin168	Swap (BOI16_swap)	C++14	68 / 100	1000 ms	238404 KB

swap

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

const int mxN=2e5, MGC1=1e6;
int n, a[mxN+1], cdi;
unordered_map<int, int> di[mxN+1];
vector<int> dp[MGC1], 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]=-1;
}

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=cdi;
			cdi=(cdi+1)%MGC1;
			dp[c].clear();
			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};
		}
	}
	for(int b : gd(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	34 ms	34808 KB	Output is correct
2	Correct	33 ms	34872 KB	Output is correct
3	Correct	35 ms	35004 KB	Output is correct
4	Correct	33 ms	35004 KB	Output is correct
5	Correct	32 ms	35004 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	34808 KB	Output is correct
2	Correct	33 ms	34872 KB	Output is correct
3	Correct	35 ms	35004 KB	Output is correct
4	Correct	33 ms	35004 KB	Output is correct
5	Correct	32 ms	35004 KB	Output is correct
6	Correct	33 ms	35004 KB	Output is correct
7	Correct	33 ms	35004 KB	Output is correct
8	Correct	34 ms	35008 KB	Output is correct
9	Correct	34 ms	35056 KB	Output is correct
10	Correct	33 ms	35060 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	34808 KB	Output is correct
2	Correct	33 ms	34872 KB	Output is correct
3	Correct	35 ms	35004 KB	Output is correct
4	Correct	33 ms	35004 KB	Output is correct
5	Correct	32 ms	35004 KB	Output is correct
6	Correct	33 ms	35004 KB	Output is correct
7	Correct	33 ms	35004 KB	Output is correct
8	Correct	34 ms	35008 KB	Output is correct
9	Correct	34 ms	35056 KB	Output is correct
10	Correct	33 ms	35060 KB	Output is correct
11	Correct	34 ms	35336 KB	Output is correct
12	Correct	36 ms	35440 KB	Output is correct
13	Correct	42 ms	35440 KB	Output is correct
14	Correct	36 ms	35872 KB	Output is correct
15	Correct	40 ms	35872 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	34808 KB	Output is correct
2	Correct	33 ms	34872 KB	Output is correct
3	Correct	35 ms	35004 KB	Output is correct
4	Correct	33 ms	35004 KB	Output is correct
5	Correct	32 ms	35004 KB	Output is correct
6	Correct	33 ms	35004 KB	Output is correct
7	Correct	33 ms	35004 KB	Output is correct
8	Correct	34 ms	35008 KB	Output is correct
9	Correct	34 ms	35056 KB	Output is correct
10	Correct	33 ms	35060 KB	Output is correct
11	Correct	34 ms	35336 KB	Output is correct
12	Correct	36 ms	35440 KB	Output is correct
13	Correct	42 ms	35440 KB	Output is correct
14	Correct	36 ms	35872 KB	Output is correct
15	Correct	40 ms	35872 KB	Output is correct
16	Correct	103 ms	50440 KB	Output is correct
17	Correct	108 ms	50440 KB	Output is correct
18	Correct	114 ms	51076 KB	Output is correct
19	Correct	439 ms	105844 KB	Output is correct
20	Correct	363 ms	105844 KB	Output is correct

Subtask #5
0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	34808 KB	Output is correct
2	Correct	33 ms	34872 KB	Output is correct
3	Correct	35 ms	35004 KB	Output is correct
4	Correct	33 ms	35004 KB	Output is correct
5	Correct	32 ms	35004 KB	Output is correct
6	Correct	33 ms	35004 KB	Output is correct
7	Correct	33 ms	35004 KB	Output is correct
8	Correct	34 ms	35008 KB	Output is correct
9	Correct	34 ms	35056 KB	Output is correct
10	Correct	33 ms	35060 KB	Output is correct
11	Correct	34 ms	35336 KB	Output is correct
12	Correct	36 ms	35440 KB	Output is correct
13	Correct	42 ms	35440 KB	Output is correct
14	Correct	36 ms	35872 KB	Output is correct
15	Correct	40 ms	35872 KB	Output is correct
16	Correct	103 ms	50440 KB	Output is correct
17	Correct	108 ms	50440 KB	Output is correct
18	Correct	114 ms	51076 KB	Output is correct
19	Correct	439 ms	105844 KB	Output is correct
20	Correct	363 ms	105844 KB	Output is correct
21	Correct	358 ms	105844 KB	Output is correct
22	Correct	347 ms	105844 KB	Output is correct
23	Correct	367 ms	105844 KB	Output is correct
24	Execution timed out	1083 ms	238404 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

답안 #76600

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