글 읽기 - lis로 풀었는데 왜 틀렸는지 모르겠습니다

jh1125kr 7년 전 0

lis방식으로 풀었는데...어떤 테스트케이스가 틀렸는지 모르겠습니다..ㅠㅠ

#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

int n;
int dp_idx[100001]; // 왼쪽 배열 저장
int dp[100001];     // 오른쪽 배열 저장
bool visited[500001]; 
vector<pair<int, int> > v(100002);

int main()
{
	int n;
	v.push_back(make_pair(0, 0));
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		v[i].first = a, v[i].second = b;
	}
	sort(v.begin(), v.begin() + n + 1);
	int idx, ans = 1;
	dp_idx[1] = v[1].first;
	dp[1] = v[1].second;
	for (int i = 2; i <= n; i++)
	{
		if (dp[ans] < v[i].second)
		{
			ans++;
			dp_idx[ans] = v[i].first;
			dp[ans] = v[i].second;
			continue;
		}
		idx = lower_bound(dp, dp + ans, v[i].second) - dp;
		dp_idx[idx] = v[i].first;
		dp[idx] = v[i].second;
	}
	for (int i = 1; i <= ans; i++)
	{
		visited[dp_idx[i]] = true; // 최장증가수열에 해당하는 왼쪽 인덱스는 true
	}
	printf("%d\n", n - ans);
	for (int i = 1; i <= n; i++)
	{
		if (visited[v[i].first] == false) // 원래 배열에서 visited에 방문하지 않은 왼쪽 인덱스는 출력
			printf("%d\n", v[i].first);
	}
}

jjwdi0 7년 전 0

10
461172 179604
450010 52741
433823 483423
281069 492282
494933 325829
370116 463789
397772 84522
283770 375649
467088 487809
385495 279870

넣어보세요

jh1125kr 7년 전 0

아아... 이게 직접 대상을 출력하는 거라 틀릴수밖에 없네요..ㅠㅠ 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

lis로 풀었는데 왜 틀렸는지 모르겠습니다

jh1125kr 7년 전 0

jjwdi0 7년 전 0

jh1125kr 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말