글 읽기 - 시간초과인데 아무리 봐도 모르겠습니다.

jin03114 3년 전 0

여러 블로그를 봐도 제가 생각해낸 방법과 모두 비슷하던데 왜 제껀 시간초과가 뜨는지 도무지 모르겠습니다...

주석은 나름대로 다 달아보았습니다.

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


struct Ball {
    int size, color, index;
    bool operator<(const Ball& b) const {
        return size < b.size;
    }
};

int n;
int Hash[200001];
int Hash2[2001];
int ans[200001];

vector<Ball> Balls;

void getInput() {
    cin >> n;
    int i, j;
    int color, size;
    for (i = 1; i <= n; i++) {
        cin >> color >> size;
        Balls.push_back({ size, color, i });
    }
    // size에 대해서 정렬을 한다.
    sort(Balls.begin(), Balls.end());

}
void Solve() {
    int i, j, cnt = 0;
    int size, color, index;
    for (i = 0; i < Balls.size(); i++) {
        size = Balls[i].size;
        color = Balls[i].color;
        index = Balls[i].index;

        //정답 배열(ans)에 여태까지 더한 (cnt - 여태까지 나온 똑같은 color들의 size - 여태까지 나온 똑같은 size들의 size)
        ans[index] = cnt - Hash[color] - Hash2[size];

        //여태까지 나온 color의 size 모두 더해놓고
        Hash[color] = Hash[color] + size;

        //여태까지 나온 size의 size 모두 더해놓고
        Hash2[size] = Hash2[size] + size;

        //현재까지 더한 size
        cnt = cnt + size;
        
        //만약 이전에 color와 size가 같은게 나왔다면 이전꺼와 같은 ans를 넣어준다.
        if (i!=0 && Balls[i-1].size == size && Balls[i-1].color== color) {
            ans[index] = ans[Balls[i-1].index];
        }
    }
    for (i = 1; i <= n;i++) {
        cout << ans[i] << endl;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    getInput();
    Solve();
    return 0;
}

3587jjh 3년 전 0

57째줄의 endl은 설령 61-62째줄을 입력했더라도 굉장히 느립니다.

cout << ans[i] << "\n";으로 바꾸면 틀렸습니다 라고 뜨지만 시간초과는 피할 수 있게 됩니다

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

문제

문제

출처

ICPC

시간초과인데 아무리 봐도 모르겠습니다.

jin03114 3년 전 0

3587jjh 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말