답안 #76601 :: oj.uz

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

swap

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

const int mxN=2e5, MGC1=8e5;
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	28 ms	30072 KB	Output is correct
2	Correct	30 ms	30240 KB	Output is correct
3	Correct	30 ms	30240 KB	Output is correct
4	Correct	28 ms	30240 KB	Output is correct
5	Correct	28 ms	30240 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	30072 KB	Output is correct
2	Correct	30 ms	30240 KB	Output is correct
3	Correct	30 ms	30240 KB	Output is correct
4	Correct	28 ms	30240 KB	Output is correct
5	Correct	28 ms	30240 KB	Output is correct
6	Correct	28 ms	30240 KB	Output is correct
7	Correct	28 ms	30260 KB	Output is correct
8	Correct	30 ms	30316 KB	Output is correct
9	Correct	29 ms	30316 KB	Output is correct
10	Correct	28 ms	30316 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	30072 KB	Output is correct
2	Correct	30 ms	30240 KB	Output is correct
3	Correct	30 ms	30240 KB	Output is correct
4	Correct	28 ms	30240 KB	Output is correct
5	Correct	28 ms	30240 KB	Output is correct
6	Correct	28 ms	30240 KB	Output is correct
7	Correct	28 ms	30260 KB	Output is correct
8	Correct	30 ms	30316 KB	Output is correct
9	Correct	29 ms	30316 KB	Output is correct
10	Correct	28 ms	30316 KB	Output is correct
11	Correct	29 ms	30572 KB	Output is correct
12	Correct	31 ms	30684 KB	Output is correct
13	Correct	31 ms	30684 KB	Output is correct
14	Correct	32 ms	31084 KB	Output is correct
15	Correct	37 ms	31084 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	30072 KB	Output is correct
2	Correct	30 ms	30240 KB	Output is correct
3	Correct	30 ms	30240 KB	Output is correct
4	Correct	28 ms	30240 KB	Output is correct
5	Correct	28 ms	30240 KB	Output is correct
6	Correct	28 ms	30240 KB	Output is correct
7	Correct	28 ms	30260 KB	Output is correct
8	Correct	30 ms	30316 KB	Output is correct
9	Correct	29 ms	30316 KB	Output is correct
10	Correct	28 ms	30316 KB	Output is correct
11	Correct	29 ms	30572 KB	Output is correct
12	Correct	31 ms	30684 KB	Output is correct
13	Correct	31 ms	30684 KB	Output is correct
14	Correct	32 ms	31084 KB	Output is correct
15	Correct	37 ms	31084 KB	Output is correct
16	Correct	97 ms	45304 KB	Output is correct
17	Correct	96 ms	45304 KB	Output is correct
18	Correct	129 ms	45488 KB	Output is correct
19	Correct	401 ms	100128 KB	Output is correct
20	Correct	362 ms	100128 KB	Output is correct

Subtask #5
0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	30072 KB	Output is correct
2	Correct	30 ms	30240 KB	Output is correct
3	Correct	30 ms	30240 KB	Output is correct
4	Correct	28 ms	30240 KB	Output is correct
5	Correct	28 ms	30240 KB	Output is correct
6	Correct	28 ms	30240 KB	Output is correct
7	Correct	28 ms	30260 KB	Output is correct
8	Correct	30 ms	30316 KB	Output is correct
9	Correct	29 ms	30316 KB	Output is correct
10	Correct	28 ms	30316 KB	Output is correct
11	Correct	29 ms	30572 KB	Output is correct
12	Correct	31 ms	30684 KB	Output is correct
13	Correct	31 ms	30684 KB	Output is correct
14	Correct	32 ms	31084 KB	Output is correct
15	Correct	37 ms	31084 KB	Output is correct
16	Correct	97 ms	45304 KB	Output is correct
17	Correct	96 ms	45304 KB	Output is correct
18	Correct	129 ms	45488 KB	Output is correct
19	Correct	401 ms	100128 KB	Output is correct
20	Correct	362 ms	100128 KB	Output is correct
21	Correct	321 ms	100128 KB	Output is correct
22	Correct	339 ms	100128 KB	Output is correct
23	Correct	569 ms	100128 KB	Output is correct
24	Execution timed out	1105 ms	263172 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

답안 #76601

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