oj.uz

Submission #56180

# Submission time Handle Problem Language Result Execution time Memory
56180 2018-07-10T07:45:15 Z 김세빈(#1581) Swap (BOI16_swap) C++11
0 / 100
 1000 ms 9956 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> V[404040];
int A[202020], R[202020], D[202020];
int n;

void dfs(int p, int v, int o)
{
	if(p > n) return;
	
	int i, j;
	
	for(i=0;i<V[p].size();i++){
		if(V[p][i] == v) break;
	}
	if(i < V[p].size()){
		if(o == 1){
			V[p][i] = -V[p][i];
		}
		else{
			if(i == 0) i = 1;
			for(j=0;j<=i;j++){
				if(V[p][j] > 0) V[p][j] = -V[p][j];
			}
			
		}
	}
	
	dfs(p<<1, v, o);
	dfs(p<<1|1, v, o);
}

void check(int t, int p)
{
	if(t & (1 << (D[t] - D[R[p]] - 1))){
		dfs(R[p]<<1|1, p, 0);
		dfs(R[p]<<1, p, 1);
	}
	else{
		dfs(R[p]<<1, p, 0);
		dfs(R[p]<<1|1, p, 1);
	}
}

int main()
{
	int i, j, m, a, b, c;
	
	scanf("%d", &n);
	
	for(i=1;i<=n;i++){
		scanf("%d", A+i);
	}
	
	for(i=2;i<=n;i++){
		D[i] = D[i>>1] + 1;
	}
	
	V[1].push_back(1);
	
	for(i=1;i<=n;i++){
		m = -1;
		for(j=0;j<V[i].size();j++){
//			printf("%d (%d)\n", V[i][j], A[V[i][j]]);
			if(V[i][j] > 0 && (m == -1 || A[V[i][j]] < A[m])) m = V[i][j];
		}
		if(m == -1) while(1);
		a = A[m];
		
		b = (i<<1) > n? 1e9 : A[i<<1];
		c = (i<<1|1) > n? 1e9 : A[i<<1|1];
		
		if(a < b && a < c){
			printf("%d ", a);
			if(V[i].size() > 1) check(i, m);
			
			V[i<<1].push_back(i<<1);
			V[i<<1|1].push_back(i<<1|1);
		}
		else if(b < c){
			printf("%d ", b);
			
			V[i<<1] = V[i];
			V[i<<1|1].push_back(i<<1|1);
		}
		else{
			printf("%d ", c);
			
			if(V[i].size() == 1) R[m] = i;
			R[i<<1] = i;
			V[i].push_back(i<<1);
			
			V[i<<1] = V[i];
			V[i<<1|1] = V[i];
		}
	}
	
	printf("\n");
	
	return 0;
}

Compilation message

swap.cpp: In function 'void dfs(int, int, int)':
swap.cpp:15:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<V[p].size();i++){
          ~^~~~~~~~~~~~
swap.cpp:18:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(i < V[p].size()){
     ~~^~~~~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:65:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<V[i].size();j++){
           ~^~~~~~~~~~~~
swap.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:54: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 11 ms 9848 KB Output is correct
2 Correct 12 ms 9956 KB Output is correct
3 Execution timed out 1082 ms 9956 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9848 KB Output is correct
2 Correct 12 ms 9956 KB Output is correct
3 Execution timed out 1082 ms 9956 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9848 KB Output is correct
2 Correct 12 ms 9956 KB Output is correct
3 Execution timed out 1082 ms 9956 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9848 KB Output is correct
2 Correct 12 ms 9956 KB Output is correct
3 Execution timed out 1082 ms 9956 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9848 KB Output is correct
2 Correct 12 ms 9956 KB Output is correct
3 Execution timed out 1082 ms 9956 KB Time limit exceeded
4 Halted 0 ms 0 KB -