글 읽기 - 시간 초과 원인을 모르겠습니다.

(追記) (追記ここまで)

시간 초과 원인을 모르겠습니다.

1655번 - 가운데를 말해요

kmj020827 5달 전 0

제가 사용한 방법으로는 절대 시간을 지킬 수 없을까요?

#include <bits/stdc++.h>
using namespace std;
vector<int>::iterator binarySearch(vector<int> &v, int &t) {
 if (v.size() == 0) {
 return v.begin();
 }
 int low = 0, high = v.size() - 1;
 while (low<=high) {
 int mid = (low+high)/2;
 if (v[mid] == t) {
 return v.begin() + mid;
 }
 else if (v[mid] < t) {
 low = mid + 1;
 }
 else {
 high = mid - 1;
 }
 }
 return v.begin() + high + 1;
}
int main() {
 ios::sync_with_stdio(false);
 cin.tie(NULL);
 cout.tie(NULL);
 int n;
 cin >> n;
 int t;
 vector<int> v, result;
 for (int i=0;i<n;i++) {
 cin >> t;
 vector<int>::iterator index = binarySearch(v, t);
 if (index == v.end()) {
 v.push_back(t);
 }
 else {
 v.insert(index, t);
 }
 if (v.size() % 2 == 0) {
 result.push_back(v[v.size()/2-1]);
 }
 else {
 result.push_back(v[v.size()/2]);
 }
 }
 for (auto i : result) {
 cout << i << "\n";
 }
 return 0;
}

zenith82114 5달 전 1

vector는 모든 원소가 연속한 주소에 위치해야 한다는 제약 때문에 insert 시 평균적으로 삽입 위치부터 오른쪽 끝까지 거리에 비례하는 시간이 걸립니다.

kmj020827 5달 전 0

알려주셔서 감사합니다!

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

시간 초과 원인을 모르겠습니다.

kmj020827 5달 전 0

zenith82114 5달 전 1

kmj020827 5달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말