글 읽기 - 18892번 도대체 어디가 틀렸는지 모르겠습니다. ㅠㅠ

rlaalswo9975 2년 전 0

4일 동안 어디가 틀렸는지 이것 저것 넣어보면서 어디가 틀렸는지 모르겠습니다..

제출하면 "틀렸습니다"가 나오는데 도대체 어디에 모순이 있는 지 모르겠습니다..

도와주세요 ㅠㅠ

알고리즘은 펜윅트리를 이용하였습니다.

#include <iostream>
#include <vector>
#include <map>
#define MAX 987654321
using namespace std;

vector<int> MAX_LEN;
//펜윅트리로 구현한 길이
vector<int> Length;
//길이
vector<long long> num;
//개수
vector<long long> MAX_NUM;
//펜윅트리로 구현한 개수
map<int,int> dict;
//dictionay <위치, 숫자>인데 숫자가 연속적으로 나오게 설정하였음
//예를 들어 1 5 6 이면 1 2 3 이 dict->first에 입력됨
//비슷한 다른 문제랑 같이 풀어서 추가하였음
map<int,int> m;
//<input data, 위치>
vector<int> transform;
//펜윅트리로 업데이트 하는 과정에서 감소하는 수열을 찾는게 좋을 것 같아서 입력받은 것의 역순으로 위치가 저장되어있음
vector<int> ans;
//출력할 벡터
vector<int> arr;
//입력한 데이터 값
int n;
//
int maxlen;
//long long maxnum;
long long k;
//skip 해야 할 개수

void update_length(int order){
  //penwick 업데이트
  //감소하는 수열을 찾을 예정
  int len = 0;
  long long tnum = 1;
  int next = order;
  while(next <=n){
    //감소하는 것이기 때문에 앞이 아닌 뒤를 탐색
    if(MAX_LEN[next]>len){
      len = MAX_LEN[next];
      tnum = MAX_NUM[next];
      if(tnum > MAX){
        tnum = MAX;
      }
    }
    else if(MAX_LEN[next] == len){
      tnum += MAX_NUM[next];
      if(tnum > MAX){
        tnum = MAX;
      }
    }
    next += (next & -next);
  }
  len++;
  Length[order] = len;
  num[order] = tnum;
  next = order ;
  while(next>=1){
    //감소하는 것이기 때문에 뒤가 아닌 앞을 갱신
    if(MAX_LEN[next] == len){
      MAX_NUM[next] += tnum;
      if(MAX_NUM[next] > MAX){
        MAX_NUM[next] = MAX;
      }
    }
    else if(MAX_LEN[next] < len){
      MAX_LEN[next] = len;
      MAX_NUM[next] = tnum;
    }
    else{
      break;
    }
    next -= (next & -next);
  }
  return;
}

void ret_S(int cur, int len, long long skip){
  if(skip<=0){
    return;
  }
  map<int, int> x;
  //<값, 위치>
  for(int i = cur+1; i<=n; i++){
    int next = dict.find(i)->second;
    if(Length[next] == len && arr[i] > arr[cur]){
      x[next] = i;
    }
    //만약 해당 조건을 만족하면 map에 추가
  }
  map<int, int>::iterator iter;

  for(iter = x.begin(); iter!=x.end(); iter++){
    int next = iter->second;
    //위치
    //개수를 좀 더 쉽게 찾기 위해서
    if(num[dict.find(next)->second] >= skip){
      //해당 개수가 skip보다 크면 답에 추가
      ans.push_back(arr[next]);
      if(len > 1){
        ret_S(next, len-1, skip);
      }
      else{
        skip = -1;
        return;
      }
      break;
    }
    else{
      //아닐 시 skip 감소
      skip -= num[next];
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  ans.clear();
  dict.clear();
  num.clear();
  Length.clear();
  MAX_LEN.clear();
  transform.clear();
  arr.clear();
  m.clear();
  MAX_NUM.clear();
  //초기화1
  cin>>n>>k;
  num.assign(n+1,0);
  Length.assign(n+1,0);
  MAX_LEN.assign(n+1,0);
  transform.assign(n+1,0);
  arr.assign(n+1,0);
  MAX_NUM.assign(n+1,0);
  maxlen = 0;
  //maxnum = 1;
  //초기화2

  for(int i = 1; i<=n; i++){
    int temp;
    cin>>temp;
    arr[i] = temp;
    m[temp] = i;
    //입력받고 m에 추가
  }
  map<int, int>::iterator mit;
  int tmp = 1;
  for(mit = m.begin(); mit!=m.end(); mit++){
    dict[mit->second] = tmp; 
    transform[n + 1 - mit->second] = tmp++;
    //연속적인 값으로 변환 및 감소수열을 찾기 위해 위치 변환
  }
  for(int i = 1; i<=n; i++){
    update_length(transform[i]);
    //입력 받은 거 update
  }
  int len = 0;
  int next = 1;
  long long tnum = 1;
  while(next <=n){
    if(MAX_LEN[next]>len){
      len = MAX_LEN[next];
    }
    next += (next & -next);
  }
  //길이 찾기
  ret_S(0,len,k);
  //정답 도출
  if(ans.size() == len){
    for(int i = 0; i<ans.size(); i++){
      cout<<ans[i];
      if(i < ans.size()-1){
        cout<<" ";
      }
    }
  }
  else{
    cout<<"-1";
  }
}

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

문제

문제

출처

ICPC

18892번 도대체 어디가 틀렸는지 모르겠습니다. ㅠㅠ

rlaalswo9975 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말