oj.uz

Submission #64031

# Submission time Handle Problem Language Result Execution time Memory
64031 2018-08-03T08:29:31 Z 김세빈(#1869) Ranklist Sorting (BOI07_sorting) C++11
30 / 100
 12 ms 804 KB 
#include <bits/stdc++.h>

using namespace std;

int A[22], B[22];
bool chk[22];
vector <int> X;
int n, v, ans;

void move(int a, int b)
{
	int i, t;
	
	if(a <= b){
		t = B[a];
		for(i=a; i<b; i++) B[i] = B[i+1];
		B[b] = t;
	}
	else{
		t = B[a];
		for(i=a; i>b; i--) B[i] = B[i-1];
		B[b] = t;
	}
}

int check(int t)
{
	int i, j, k, ret = 0;
	vector <int> V;
	
	V.push_back(0);
	for(i=1; i<=n; i++){
		if(t & (1 << i-1)){
			V.push_back(A[i]);
			chk[A[i]] = 1;
		}
		else chk[A[i]] = 0;
		B[i] = A[i];
	}
	
	for(;;){
		for(i=1; i<=n; i++) if(!chk[B[i]]) break;
		if(i > n) break;
		
		for(k=0; k<V.size(); k++){
			if(V[k] >= B[i]) break;
		} k --;
		
		for(j=0; j<n; j++) if(B[j] == V[k]) break;
		if(i > j) j ++;
		
		V.push_back(B[i]);
		chk[B[i]] = 1;
		
		for(k=V.size()-1; k>0; k--){
			if(V[k] < V[k-1]) swap(V[k], V[k-1]);
		}
		
		ret += i + j;
		move(i, j);
	}
	
	return ret;
}

void print(int t)
{
	int i, j, k, s = 0;
	vector <int> V;
	
	V.push_back(0);
	for(i=1; i<=n; i++){
		if(t & (1 << i-1)){
			V.push_back(A[i]);
			chk[A[i]] = 1;
		}
		else chk[A[i]] = 0, s ++;
		B[i] = A[i];
	}
	
	printf("%d\n", s);
	
	for(;;){
		for(i=1; i<=n; i++) if(!chk[B[i]]) break;
		if(i > n) break;
		
		for(k=0; k<V.size(); k++){
			if(V[k] >= B[i]) break;
		} k --;
		
		for(j=0; j<n; j++) if(B[j] == V[k]) break;
		if(i > j) j ++;
		
		V.push_back(B[i]);
		chk[B[i]] = 1;
		
		for(k=V.size()-1; k>0; k--){
			if(V[k] < V[k-1]) swap(V[k], V[k-1]);
		}
		
		printf("%d %d\n", i, j);
		move(i, j);
	}
}

int main()
{
	int i, j, p, k;
	
	v = 1e9;
	
	scanf("%d", &n);
	
	for(i=1; i<=n; i++){
		scanf("%d", A+i);
		X.push_back(A[i]);
	}
	
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	
	for(i=1; i<=n; i++){
		A[i] = X.end() - lower_bound(X.begin(), X.end(), A[i]);
	}
	
	for(i=1; i<(1<<n); i++){
		p = 0;
		for(j=1; j<=n; j++){
			if(i & (1 << j-1)){
				if(A[p] > A[j]) break;
				p = j;
			}
		}
		if(j <= n) continue;
		k = check(i);
		if(k < v) v = k, ans = i;
	}
	
	print(ans);
	
	return 0;
}

Compilation message

sorting.cpp: In function 'int check(int)':
sorting.cpp:33:17: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   if(t & (1 << i-1)){
                ~^~
sorting.cpp:45:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(k=0; k<V.size(); k++){
            ~^~~~~~~~~
sorting.cpp: In function 'void print(int)':
sorting.cpp:73:17: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   if(t & (1 << i-1)){
                ~^~
sorting.cpp:87:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(k=0; k<V.size(); k++){
            ~^~~~~~~~~
sorting.cpp: In function 'int main()':
sorting.cpp:129:18: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    if(i & (1 << j-1)){
                 ~^~
sorting.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sorting.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A+i);
   ~~~~~^~~~~~~~~~~

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Incorrect 4 ms 356 KB Unexpected end of file - int32 expected
5 Runtime error 3 ms 688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 2 ms 744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 12 ms 744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 2 ms 804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 804 KB Execution killed with signal 11 (could be triggered by violating memory limits)