글 읽기 - 정올에서는 맞는데 백준에서는 틀립니다... 반례나 문제를 찾을 수 있을까요?

cjs 4년 전 0

제목 그대로 정올에서는 Accept 가 뜨는데 여기서는 통과가 되지 않네요...

혹시 반례를 알 수 있을까요??

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

int N;
int maps[500001];
int mapB[500001];
int DP[100001];
int save[100001];

int main() {
	int tmp1, tmp2,tsave=0,length = 1,maxI = 0,minI = 500001;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmp1 >> tmp2;
		maps[tmp1] = tmp2;
		mapB[tmp2] = tmp1;
		maxI = maxI > tmp1 ? maxI : tmp1;
		minI = minI < tmp1 ? minI : tmp1;
	}
	DP[1] = maps[minI];
	for (int i = minI+1; i <= maxI; i++) {
		if (maps[i] == 0) continue;
		if (DP[length] < maps[i]) {
			DP[++length] = maps[i];
			continue;
		}
		tmp1 = lower_bound(DP + 1, DP + length + 1, maps[i]) - DP;
		save[tsave++] = mapB[DP[tmp1]];
		DP[tmp1] = maps[i];
	}
	cout << N - length << "\n";
	for (int i = 0; i < tsave; i++)
		cout << save[i] << "\n";
}

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

문제

문제

출처

ICPC

정올에서는 맞는데 백준에서는 틀립니다... 반례나 문제를 찾을 수 있을까요?

cjs 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말