글 읽기 - 테스트케이스 추가 요청

thak00 5년 전 0

7580819 번 채점번호 코드 검토후 테스트케이스 추가 요청합니다. std::vector 에 erase 연산때문에 O(N^2) 코드인데 맞았습니다가 뜨네요 테스트케이스 추가 요청합니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    vector < int > List;
    int N, M, Flag_Index = 0, T = 0;
    cin >> N >> M;
    Flag_Index = M - 1;
    for (int i = 1; i < N + 1; ++i) {
        List.push_back(i);
    }
    cout << '<';
    for (int j, i = 0; i < N; ) {
        for (j = Flag_Index; j < N - T; j += M - 1) {
            cout << List[j] << (i == N - 1 ? ">" : ", ");
            List.erase(List.begin() + j);
            ++T; ++i;
        }
        Flag_Index = j % ((N - T) ? (N - T) : 1);
    }
}

jh05013 5년 전 0

O(N^2)이지만 정말로 N*N 루프를 다 도는 게 아니기 때문에 최대 케이스를 넣어 봐도 시간 내에 돌아감을 확인할 수 있습니다.

djm03178 5년 전 0

뿐만 아니라 vector::erase는 memmove를 사용하여 매우, 매우 빠르기 때문에 설령 10만개를 10만번 옮긴다고 해도 생각보다 훨씬 빠릅니다.

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

문제

문제

출처

ICPC

테스트케이스 추가 요청

thak00 5년 전 0

jh05013 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말