oj.uz

Submission #56204

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

const int N = 200005, inf = 1e9;

int n, a[N];

vector<pii> dt[N];

int geti (int I, int J) {
	for(int i=0;i<dt[I].size();i++) {
		if(dt[I][i].X > J) return dt[I][i-1].Y;
	}
	return dt[I].back().Y;
}

void calc (int I) {
	dt[I].push_back({0, I});
	if(2*I+1 > n) {
		if(2*I <= n) dt[I].push_back({a[2*I], 2*I});
	}
	else if(a[2*I] < a[2*I+1]) {
		dt[I].push_back({a[2*I], 2*I});
		for(auto &T : dt[2*I]) {
			if(T.X <= a[2*I]) continue;
			dt[I].push_back(T);
		}
	}
	else {
		dt[I].push_back({a[2*I+1], 2*I+1});
		for(int i=0,j=0;;) {
			auto &P = dt[2*I][i], &Q = dt[2*I+1][j];
			if(max(P.X, Q.X) > a[2*I+1]) dt[I].push_back({max(P.X, Q.X), min(P.Y, Q.Y)});
			bool A = (i+1 == dt[2*I].size()), B = (j+1 == dt[2*I+1].size());
			if(A && B) break;
			else if(A) j++;
			else if(B) i++;
			else if(dt[2*I][i+1] < dt[2*I+1][j+1]) i++;
			else j++;
		}
	}
}

void exec (int I) {
	if(2*I+1 > n) {
		if(2*I <= n && a[I] > a[2*I]) swap(a[I], a[2*I]);
	}
	else if(a[I] < a[2*I] && a[I] < a[2*I+1]) return;
	else if(a[2*I] < a[2*I+1]) swap(a[I], a[2*I]);
	else {
		int A = a[I], B = a[2*I];
		if(A > B) swap(A, B);
		a[I] = a[2*I+1];
		if(geti(2*I, A) < geti(2*I+1, A)) {
			a[2*I] = A;
			a[2*I+1] = B;
		}
		else {
			a[2*I] = B;
			a[2*I+1] = A;
		}
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
	for(int i=n;i>=1;i--) calc(i);
	for(int i=1;i<=n;i++) exec(i);
	for(int i=1;i<=n;i++) {
		printf("%d ",a[i]);
	}
}

Compilation message

swap.cpp: In function 'int geti(int, int)':
swap.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<dt[I].size();i++) {
              ~^~~~~~~~~~~~~
swap.cpp: In function 'void calc(int)':
swap.cpp:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    bool A = (i+1 == dt[2*I].size()), B = (j+1 == dt[2*I+1].size());
              ~~~~^~~~~~~~~~~~~~~~~
swap.cpp:37:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    bool A = (i+1 == dt[2*I].size()), B = (j+1 == dt[2*I+1].size());
                                           ~~~~^~~~~~~~~~~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
swap.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 7 ms 5268 KB Output is correct
4 Correct 7 ms 5268 KB Output is correct
5 Correct 7 ms 5268 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 7 ms 5268 KB Output is correct
4 Correct 7 ms 5268 KB Output is correct
5 Correct 7 ms 5268 KB Output is correct
6 Correct 6 ms 5268 KB Output is correct
7 Incorrect 6 ms 5268 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 7 ms 5268 KB Output is correct
4 Correct 7 ms 5268 KB Output is correct
5 Correct 7 ms 5268 KB Output is correct
6 Correct 6 ms 5268 KB Output is correct
7 Incorrect 6 ms 5268 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 7 ms 5268 KB Output is correct
4 Correct 7 ms 5268 KB Output is correct
5 Correct 7 ms 5268 KB Output is correct
6 Correct 6 ms 5268 KB Output is correct
7 Incorrect 6 ms 5268 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 7 ms 5268 KB Output is correct
4 Correct 7 ms 5268 KB Output is correct
5 Correct 7 ms 5268 KB Output is correct
6 Correct 6 ms 5268 KB Output is correct
7 Incorrect 6 ms 5268 KB Output isn't correct
8 Halted 0 ms 0 KB -