oj.uz

Submission #56155

# Submission time Handle Problem Language Result Execution time Memory
56155 2018-07-10T06:25:49 Z 김현수(#2106) Swap (BOI16_swap) C++11
0 / 100
 2 ms 440 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;

const int N = 200005;

int n, a[N];

int solve (int I, int V) {
	if(2*I+1 > n) {
		if(2*I <= n && a[2*I] < V) return 2*I;
		return I;
	}
	if(a[2*I] > V && a[2*I+1] > V) return I;
	if(a[2*I] < a[2*I+1]) return solve(2*I, V);
	return min(solve(2*I, V), solve(2*I+1, V));
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++) {
		if(2*i > n) continue;
		else if(2*i+1 > n) {
			if(a[2*i] < a[i]) swap(a[2*i], a[i]);
		}
		else {
			if(a[2*i+1] < a[i] && a[2*i+1] < a[2*i]) {
				pii A = min((pii){solve(2*i, a[i]), a[i]}, (pii){solve(2*i+1, a[2*i]), a[2*i]});
				pii B = min((pii){solve(2*i, a[2*i]), a[2*i]}, (pii){solve(2*i+1, a[i]), a[i]});
				if(A < B) swap(a[i], a[2*i]);
				swap(a[i], a[2*i+1]);
			}
			else if(a[2*i] < a[i] && a[2*i] < a[2*i+1]) {
				swap(a[i], a[2*i]);
			}
		}
	}
	for(int i=1;i<=n;i++) {
		printf("%d ",a[i]);
	}
}

Compilation message

swap.cpp: In function 'int main()':
swap.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
swap.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Incorrect 2 ms 440 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Incorrect 2 ms 440 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Incorrect 2 ms 440 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Incorrect 2 ms 440 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Incorrect 2 ms 440 KB Output isn't correct
5 Halted 0 ms 0 KB -