답안 #201450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
201450 2020-02-10T15:27:03 Z red1108 Swap (BOI16_swap) C++17
100 / 100
781 ms 3832 KB
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define eb emplace_back
#define em emplace
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;typedef long double ld;typedef unsigned long long ul;typedef unsigned int ui;typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 2e18;
const int inf = 2e9;
template<class T>
void pr(T t) {cout << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cout << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cout << endl;}

int in[200010],n;
int f(int x, int v){
	if(x>n/2) return x;
	if(v<in[x*2]&&v<in[x*2+1]) return x;
	if(in[x*2]<v&&in[x*2]<in[x*2+1]) return f(x*2,v);
	if(v<in[x*2]) return min(f(x*2,v),f(x*2+1,v));
	else{
		int a = f(x*2,in[x*2]), b = f(x*2+1,in[x*2]);
		if(a<b) return f(x*2+1,v);
		else return f(x*2,v);
	}
}
int main(){
	//freopen("input.txt","r",stdin);
	fastio;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>in[i];
	in[n+1]=n+1;
	for(int i=1;i<=n/2;i++){
		if(in[i]<in[i*2]&&in[i]<in[i*2+1]) continue;
		if(in[i*2]<in[i]&&in[i*2]<in[i*2+1]){swap(in[i],in[i*2]);continue;}

		int x = min(in[i],in[i*2]),y=max(in[i],in[i*2]),z=in[i*2+1];
		int a = f(i*2,x), b = f(i*2+1,x);
		if(a<b) {in[i*2]=x;in[i*2+1]=y;}
		else {in[i*2]=y;in[i*2+1]=x;}
		in[i]=z;
	}
	for(int i=1;i<=n;i++) cout<<in[i]<<" ";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 380 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 380 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 16 ms 1144 KB Output is correct
17 Correct 17 ms 1144 KB Output is correct
18 Correct 18 ms 1272 KB Output is correct
19 Correct 99 ms 1144 KB Output is correct
20 Correct 97 ms 1148 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 380 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 16 ms 1144 KB Output is correct
17 Correct 17 ms 1144 KB Output is correct
18 Correct 18 ms 1272 KB Output is correct
19 Correct 99 ms 1144 KB Output is correct
20 Correct 97 ms 1148 KB Output is correct
21 Correct 51 ms 3704 KB Output is correct
22 Correct 50 ms 3704 KB Output is correct
23 Correct 49 ms 3704 KB Output is correct
24 Correct 780 ms 3832 KB Output is correct
25 Correct 781 ms 3832 KB Output is correct