답안 #76597 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
76597	2018-09-15T06:29:02 Z	tmwilliamlin168	Swap (BOI16_swap)	C++14	68 / 100	884 ms	263168 KB

swap

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

const int mxN=2e5, MGC1=62000*18*2;
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;
			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	57 ms	63680 KB	Output is correct
2	Correct	55 ms	63736 KB	Output is correct
3	Correct	59 ms	63920 KB	Output is correct
4	Correct	56 ms	64144 KB	Output is correct
5	Correct	59 ms	64144 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	63680 KB	Output is correct
2	Correct	55 ms	63736 KB	Output is correct
3	Correct	59 ms	63920 KB	Output is correct
4	Correct	56 ms	64144 KB	Output is correct
5	Correct	59 ms	64144 KB	Output is correct
6	Correct	57 ms	64144 KB	Output is correct
7	Correct	58 ms	64144 KB	Output is correct
8	Correct	59 ms	64172 KB	Output is correct
9	Correct	64 ms	64180 KB	Output is correct
10	Correct	57 ms	64284 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	63680 KB	Output is correct
2	Correct	55 ms	63736 KB	Output is correct
3	Correct	59 ms	63920 KB	Output is correct
4	Correct	56 ms	64144 KB	Output is correct
5	Correct	59 ms	64144 KB	Output is correct
6	Correct	57 ms	64144 KB	Output is correct
7	Correct	58 ms	64144 KB	Output is correct
8	Correct	59 ms	64172 KB	Output is correct
9	Correct	64 ms	64180 KB	Output is correct
10	Correct	57 ms	64284 KB	Output is correct
11	Correct	59 ms	64572 KB	Output is correct
12	Correct	66 ms	64572 KB	Output is correct
13	Correct	60 ms	64572 KB	Output is correct
14	Correct	61 ms	65012 KB	Output is correct
15	Correct	61 ms	65032 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	63680 KB	Output is correct
2	Correct	55 ms	63736 KB	Output is correct
3	Correct	59 ms	63920 KB	Output is correct
4	Correct	56 ms	64144 KB	Output is correct
5	Correct	59 ms	64144 KB	Output is correct
6	Correct	57 ms	64144 KB	Output is correct
7	Correct	58 ms	64144 KB	Output is correct
8	Correct	59 ms	64172 KB	Output is correct
9	Correct	64 ms	64180 KB	Output is correct
10	Correct	57 ms	64284 KB	Output is correct
11	Correct	59 ms	64572 KB	Output is correct
12	Correct	66 ms	64572 KB	Output is correct
13	Correct	60 ms	64572 KB	Output is correct
14	Correct	61 ms	65012 KB	Output is correct
15	Correct	61 ms	65032 KB	Output is correct
16	Correct	147 ms	79496 KB	Output is correct
17	Correct	126 ms	79628 KB	Output is correct
18	Correct	129 ms	80300 KB	Output is correct
19	Correct	389 ms	135120 KB	Output is correct
20	Correct	375 ms	135120 KB	Output is correct

Subtask #5
0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	63680 KB	Output is correct
2	Correct	55 ms	63736 KB	Output is correct
3	Correct	59 ms	63920 KB	Output is correct
4	Correct	56 ms	64144 KB	Output is correct
5	Correct	59 ms	64144 KB	Output is correct
6	Correct	57 ms	64144 KB	Output is correct
7	Correct	58 ms	64144 KB	Output is correct
8	Correct	59 ms	64172 KB	Output is correct
9	Correct	64 ms	64180 KB	Output is correct
10	Correct	57 ms	64284 KB	Output is correct
11	Correct	59 ms	64572 KB	Output is correct
12	Correct	66 ms	64572 KB	Output is correct
13	Correct	60 ms	64572 KB	Output is correct
14	Correct	61 ms	65012 KB	Output is correct
15	Correct	61 ms	65032 KB	Output is correct
16	Correct	147 ms	79496 KB	Output is correct
17	Correct	126 ms	79628 KB	Output is correct
18	Correct	129 ms	80300 KB	Output is correct
19	Correct	389 ms	135120 KB	Output is correct
20	Correct	375 ms	135120 KB	Output is correct
21	Correct	394 ms	135120 KB	Output is correct
22	Correct	341 ms	135120 KB	Output is correct
23	Correct	344 ms	135120 KB	Output is correct
24	Runtime error	884 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-

답안 #76597

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