글 읽기 - 으앙 대체 왜 틀린 거야!

dohyeokkim 8년 전 1

제발 틀린 테스트 케이스 하나만 주십쇼 굽신굽신

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

typedef pair<int, int> cons;

bool comp(const cons &x, const cons &y) {
	if (x.second != y.second)
		return x.second < y.second;
	else
		return x.first < y.first;
}

int main() {
	int n, ans = 0, a, b, idx = 0;
	vector<cons> V;
	int memo[100000];
	int history[100000];
	priority_queue<int, vector<int>, greater<int>> PQ;

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d %d", &a, &b);
		V.push_back(make_pair(a, b));
	}

	sort(V.begin(), V.end(), comp);

	for (int i = 0; i < n; i++) {
		int tmp = 1;
		history[i] = i;
        
		for (int j = 0; j < i; j++) {
			if (V[j].first < V[i].first) {
				if (tmp < memo[j] + 1) {
					tmp = memo[j] + 1;
					history[i] = j;
				}
			}
		}
        
		memo[i] = tmp;

        if (ans <= memo[i]) {
            ans = memo[i];
            idx = i;
        }
    }
    
    while (history[idx] != idx) {
        for (int i = history[idx] + 1; i < idx; i++)
            PQ.push(V[i].first);
        idx = history[idx];
    }
    
    for (int i = 0; i < idx; i++){
        PQ.push(V[i].first);
    }

    printf("%d\n", n - ans);

    while (!PQ.empty()) {
        printf("%d\n", PQ.top());
        PQ.pop();
    }

    return 0;
}

kimdr123 8년 전 0

정올가서 테스트 해보시길!

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

CPU Result
6
281069
385495
397772
450010
461172
494933

You Result
6
385495
397772
450010
461172
494933

라고 나오네요.