KLIS가 계속 오답이 뜹니다. junyoung2 오버플로를 막기위해서countLis가 5000000000 초과할 때 countLis가 5000000000를 반환하도록 만들어도(countLis는 long long을 반환합니다) 오답이 나옵니다. k가 무슨 입력이 들어와도 처리할 수 있게 k도 long long으로 받았습니다. 아래에 소스코드를 첨부합니다. #include<iostream> #include<cstring> #include<vector> #include<algorithm> using namespace std; int seq[500]; int size; long long skip; long long k; int cache[501]; long long cache2[501]; vector<int> result; int lis(int x) { int& ret = cache[x]; if(ret != -1) return ret; ret = 1; for(int i = x + 1; i < size; i++) { if(seq[i] > seq[x]) { ret = max(ret, 1 + lis(i)); } } return ret; } int lisSize() { int ret = 0; for(int i = 0; i < size; i++) { ret = max(ret, lis(i)); } return ret; } long long countLis(int x) { long long& ret = cache2[x]; if(ret != -1) return ret; ret = 0; if(lis(x) == 1) return ret = 1; for(int i = x + 1; i < size; i++) { if((lis(i) == lis(x) - 1) && (seq[x] < seq[i])) { ret += countLis(i); if(ret > 5000000000) ret = 5000000000; } } return ret; } void getK(int prev, int len, int x) { if(len == 0) return; vector<int> search; int index; if(skip == k - 1) { for(int i = 0; i < size; i++) { if(lis(i) == len) search.push_back(seq[i]); } sort(search.begin(), search.end()); for(int i = 0; i < search.size(); i++) { for(int j = 0; j < size; j++) { if(search[i] == seq[j]) index = j; } if(countLis(index) <= skip) skip -= countLis(index); else { result.push_back(seq[index]); getK(seq[index], len - 1, index + 1); return; } } } for(int i = x; i < size; i++) { if(lis(i) == len && seq[i] > prev) search.push_back(seq[i]); } sort(search.begin(), search.end()); for(int i = 0; i < search.size(); i++) { for(int j = x; j < size; j++) { if(search[i] == seq[j]) index = j; } if(countLis(index) <= skip) skip -= countLis(index); else { result.push_back(seq[index]); getK(seq[index], len - 1, index + 1); return; } } } int main() { int cases; cin >> cases; while(cases--) { memset(cache, -1, sizeof(cache)); for(int i = 0; i < 501; i++) { cache2[i] = -1; } cin >> size >> k; skip = k - 1; for(int i = 0; i < size; i++) cin >> seq[i]; getK(0, lisSize(), 0); cout << lisSize() << endl; for(int i = 0; i < result.size(); i++) cout << result[i] << " "; cout << endl; result.clear(); } return 0; } 6년 전
0개의 댓글이 있습니다. 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
junyoung2
오버플로를 막기위해서countLis가 5000000000 초과할 때 countLis가 5000000000를 반환하도록 만들어도(countLis는 long long을 반환합니다) 오답이 나옵니다. k가 무슨 입력이 들어와도 처리할 수 있게 k도 long long으로 받았습니다.
아래에 소스코드를 첨부합니다.
6년 전