글 읽기 - 반례부탁드립니다. C++입니다.

dlssrb7777 4년 전 0

STLdeque는 임의의 인덱스에 있는 원소를 O(1)으로 접근할 수 있어서 총 복잡도도 O(N)이구요.

틀렸다고 나오는데 아무리 생각해도 반례가 떠오르질 않네요 반례 하나만 부탁드립니다.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);


    int n,i,l,c,co;
    deque<int> s, p, o;
    deque<int> r (500010, 0);

    cin >> n;
    for(i=0; i<n; i++){
        scanf("%d", &l);
        s.push_back(l);
    }

    for(i=0; i<n; i++){
        c=s.back();
        s.pop_back();

        while(!p.empty() && p.back() <= c){
            p.pop_back();
            co=o.back();
            o.pop_back();
            r[co] = n-i;
        }

        p.push_back(c);
        o.push_back(n-i);
    }
    

    for (i=1; i<=n; i++){
        cout << r[i] << " ";
    }


    return 0;
}

djm03178 4년 전 1

sync_with_stdio(0)을 한 뒤에는 scanf와 cin을 혼용하면 안 됩니다.

dlssrb7777 4년 전 0

@djm03178 으아아 감사합니다!

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

문제

문제

출처

ICPC

반례부탁드립니다. C++입니다.

dlssrb7777 4년 전 0

djm03178 4년 전 1

dlssrb7777 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말