Submission #155928


Source Code Expand

#include <iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int inf = 99999999;
#define index_of(as, x) \
  distance(as.begin(), lower_bound(as.begin(), as.end(), x))
int lis(const vector<int>& a) {
  const int n = a.size();
  vector<int> A(n, inf);
  vector<int> id(n);
  for (int i = 0; i < n; ++i) {
    id[i] = index_of(A, a[i]);
    A[ id[i] ] = a[i];
  }
  int m = *max_element(id.begin(), id.end());
  vector<int> b(m+1);
  for (int i = n-1; i >= 0; --i)
    if (id[i] == m) b[m--] = a[i];
  return b.size();
}
int main(){
	int i,n,x;
	vector<int> a;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&x);
		a.push_back(x);
	}
	printf("%d\n",n-lis(a));
	return 0;
}

Submission Info

Submission Time
Task D - トランプ挿入ソート
User choda310
Language C (GCC 4.6.4)
Score 0
Code Size 744 Byte
Status CE

Compile Error

./Main.c:1:20: fatal error: iostream: No such file or directory
compilation terminated.