글 읽기 - 나무재테크, K의 값이 7만 넘어가면 에러가 납니다

hannnn 3년 전 0

풀이 제출했더니 시간초과가 나와서

반례를 찾아보니까 아래 두 반례가 안되던데 어디서 틀렸는지 알 수 있을까요?

10 1 1000

100 100 100 100 100 100 100 100 100 100

1 1 1

정답: 5443

오답: 1

5 2 7
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 1 3
3 2 3

정답: 71

오답: 2

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct tree{
    int _x,_y,_z;
};
bool cmp(const tree &p1, const tree &p2){
    if(p1._z < p2._z) return true;
}

int n,m,k;
int A[10][10]; // S2D2가 뿌리는 양분
int Land[10][10]; // 각 칸에 있는 양분의 양
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
vector<tree> v;
vector<tree> tmp;
queue<tree> q;

void plant(int x, int y){
    for(int i=0; i<8; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
        v.push_back({nx,ny,1});
    }
}

int main(){
    cin >> n >> m >> k;
    int x,y,z;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> A[i][j];
            Land[i][j] = 5;
        }
    }
    for(int i=0; i<m; i++){
        tree T;
        cin >> T._x >> T._y >> T._z; // 나무 위치, 나이
        T._x -=1; T._y -=1;
        v.push_back(T);
    }
    while(k--){     
        sort(v.begin(), v.end(), cmp);

        // 봄 -> 성장기 & 죽은 나무
        for(int j=0; j<v.size(); j++){
            tree T = v[j];
            if(Land[T._x][T._y] >= T._z) {
                // cout << "click\n";
                Land[T._x][T._y] -= T._z;
                T._z += 1;
                tmp.push_back(T); // 산 나무 저장
            }
            else{ // 죽은 나무(queue)
                q.push(T);
            }
        }
        v.swap(tmp); tmp.clear();
        // 여름 -> 거름
        while(!q.empty()){
            int tx = q.front()._x;
            int ty = q.front()._y;
            int tz = q.front()._z;
            q.pop();
            Land[tx][ty] += tz/2;
        }
        // 가을 -> 번식
        for(int j=0; j<v.size(); j++){
            tree T = v[j];
            if(T._z%5==0) plant(T._x,T._y);
        }
        // 겨울 -> 양분 추가
        for(int j=0; j<n; j++){
            for(int k=0; k<n; k++){
                Land[j][k] += A[j][k];
            }
        }
    }
    cout << v.size();
    return 0;
}

seico75 3년 전 1

한번 정렬하면

자라는 나무는 순서 유지가 되고 새로 심는 나무는 항상 제일 앞이니 매번 소트할 필요 없습니다.

vector대신 deque를 쓰면 앞에 넣는 것도 문제 없을 것 같네요.

전체를 하나로 관리하지 않고 셀별로 deque쓰는 것도 가능합니다

hannnn 3년 전 0

@seico75

한 번만 소트하고, 셀별로 deque로 해서 풀었습니다.

감사합니다

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

문제

문제

출처

ICPC

나무재테크, K의 값이 7만 넘어가면 에러가 납니다

hannnn 3년 전 0

seico75 3년 전 1

hannnn 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말