글 읽기 - deque 이용해서 sort 했는데도 시간초과가 뜹니다ㅠㅠ

dnflekals 2년 전 0

처음에 heap 정렬 이용해서 풀었는데 시간초과 떠서, deque를 이용했는데도 시간초과가 뜹니다...

고수님들 시간 괜찮다면 한번만 봐주실 수 있나요??ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <functional>
#include <map>
using namespace std;
int n, m, k;
int nut[15][15];
int winter[15][15];
//priority_queue <pair<int, pair<int, int>>,vector<pair<int, pair<int, int>>>,greater<pair<int, pair<int, int>>>> pq;
deque <pair<int, pair<int, int>>> tree;
int dir[8][2] = { {1,-1},{1,0},{1,1},{0,-1},{0,1},{-1,-1},{-1,0},{-1,1} };

bool cmp(pair<int, pair<int, int>> &a, pair<int, pair<int, int>> &b) {
    return a.first < b.first;
}
int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> winter[i][j];
            nut[i][j] = 5;
        }
    }
    for (int i = 0;i < m;i++) {
        int x, y, z; cin >> x >> y >> z;
        tree.push_back({ z,{x,y} });
    }

    while (k--) {
        queue <pair<int, pair<int, int>>> q;
        queue <pair<int, pair<int, int>>> death;

        //spring
        sort(tree.begin(), tree.end(),cmp);
        while (!tree.empty()) {
            int row = tree.front().second.first;
            int col = tree.front().second.second;
            int age = tree.front().first;
            tree.pop_front();

            if (age <= nut[row][col]) {
                nut[row][col] -= age;
                q.push({ age + 1,{row,col} });
            }
            else death.push({ age,{row,col} });
        }

        //summer
        while (!death.empty()) {
            int row = death.front().second.first;
            int col = death.front().second.second;
            int age = death.front().first;
            death.pop();

            nut[row][col] += age / 2;
        }

        //fall
        while (!q.empty()) {
            int row = q.front().second.first;
            int col = q.front().second.second;
            int age = q.front().first;
            q.pop();

            if (age % 5 == 0) {
                for (int i = 0;i < 8;i++) {
                    int nrow = row + dir[i][0];
                    int ncol = col + dir[i][1];
                    if (nrow <= 0 || nrow > n || ncol <= 0 || ncol > n) continue;

                    tree.push_back({ 1,{nrow,ncol} });
                }
            }
            tree.push_back({ age,{row,col} });
        }

        //winter
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= n;j++) {
                nut[i][j] += winter[i][j];
            }
        }
    }

    int ans = tree.size();
    cout << ans << "\n";
    return 0;
}

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

문제

문제

출처

ICPC

deque 이용해서 sort 했는데도 시간초과가 뜹니다ㅠㅠ

dnflekals 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말