글 읽기 - c++ 게시판 반례는 다 되는데 1퍼센트에서 틀립니다

jack3319 2년 전 0

a는 가장 긴 부분 수열의 크기를 구하기 위한 벡터고 ans에 가장 긴 부분 수열을 넣었습니다.

a에 원소 추가하는거는 lcs O(log n)으로 풀이하는 방식이고 원소 추가할때마다 ans와 a 가 맨 뒤부터 연속적으로 다른 것만 ans에 넣어주었습니다.

가장 긴 증가하는 부분 수열2에서 나온 수열을 변형해서 출력했고 게시판에 있는 반례도 다 정상적으로 되는데 계속 1퍼센트에서 틀렸습니다가 나와서 어디가 틀렸는지 알려주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, cnt;
vector<int> a, ans;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);

	a.push_back(-1000000001);
	ans.push_back(-1000000001);
	cin >> n;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if(a.back() < x) {
			a.push_back(x);
			int check = 0, j;
			for(j = cnt; j >= 1; j--) {
				if(a[j] != ans[j])	check++;
				else	break;
			}
			for(int k = j; k <= cnt; k++) {
				ans[k] = a[k];
			}
			ans.push_back(x);
			cnt++;
		}
		else if(a.back() > x) {
			vector<int>::iterator idx = lower_bound(a.begin(), a.end(), x);
			*idx = x;
		}
	}
	cout << cnt << "\n";
	for(int i = 1; i <= cnt; i++) {
		cout << ans[i] << " ";
	}
	cout << "\n";
	return 0;
}

popoli31 2년 전 11

다음 반례를 확인해 보세요.

3 1 4 6 2 2 0 3 6

jack3319 2년 전 0

감사합니다 덕분에 잘 해결했어요

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

문제

문제

출처

ICPC

c++ 게시판 반례는 다 되는데 1퍼센트에서 틀립니다

jack3319 2년 전 0

popoli31 2년 전 11

jack3319 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말