4053. 전국민 건강 프로젝트

4053. 전국민 건강 프로젝트

시뮬레이션 문제 같은데 푸는데 꽤나 시간이 걸렸다.. 

문제의 조건을 보니 시간초과를 해결하는게 가장 중요해 보였다.

맨 처음에는 -> <- 이렇게 만나는 지점을 구하고, 그걸 찾아가면서 문제를 풀었더니 시간초과가 발생했다.

-><- 이 부분을 미리 알고 체크하고, 그걸 이용해서 문제를 풀어야 할 것 같았는데 방법이 잘 생각이 안났다.

수의 범위가 너무나 커서 배열로 하기도 그렇고.. 그래서 생각하던 중에 만들면서 큐에 집어넣는 방식으로 문제를 풀었다.

그리고 처음에 -><- 한번만 구했었는데, 생각해보니 0 인 부분( 사람이 만나는 부분)은 사실 -> 와 <- 역할을 할 수 있다. 

따라서 그 부분만을 계속 적으로 0으로 만들면서, 그니까 사람이 만나는 부분을 계속 만들고

마지막에 for문 한번으로 사람이 안만나는 것들을 정리해주면 된다.

<정답 코드>

#include<iostream>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;
int N, Q;
long long T;
 
typedef struct {
    long long p;
    long long d;
}person;
person per[100001];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        memset(per, 0, sizeof(per));
        queue<int> q;
        cin >> N >> T >> Q;
        
        for (int i = 0; i < N; i++)
        {
            cin >> per[i].p >> per[i].d;
            if (per[i].d == 2)
            {
                per[i].d = -1;
            }
        }
 
 
        // -> <- 사람이 만나는 부분 큐에 넣기
        for (int i = 0; i < N - 1; i++)
        {
            if (per[i].d == 1 && per[i+1].d == -1)
            {
                q.push(i);
                i++;
            }
        }
 
        // 사람이 만나는 부분 계속 업데이트
        while (!q.empty())
        {
            int i = q.front();
            q.pop();
 
            if (per[i].d == 0 && per[i + 1].d == 0)
            {
                continue;
            }
 
            if (i + 1 < N)
            {
                long long p1 = per[i].p + per[i].d*T;
                long long p2 = per[i + 1].p + per[i + 1].d*T;
 
 
                //-> <- 부분 체크
                if (per[i].d == 1 && per[i + 1].d == -1 && p1 >= p2)
                {
                    if (i + 1 < N)
                    {
                        q.push(i + 1);
                    }
                    if (i - 1 >= 0)
                    {
                        q.push(i - 1);
                    }
                    per[i].d = 0;
                    per[i + 1].d = 0;
                    per[i].p = per[i + 1].p = (per[i].p + per[i + 1].p) / 2;
                }
                // -> 0  이 부분 체크
                else if (per[i].d == 1 && per[i + 1].d == 0 && p1 >= p2)
                {
                    if (i - 1 >= 0)
                    {
                        q.push(i - 1);
                    }
                    if (i + 1 < N)
                    {
                        q.push(i + 1);
                    }
                    per[i].d = 0;
                    per[i].p = per[i + 1].p;
                }
 
                // 0 <-  이부분 체크
                else if (per[i].d == 0 && per[i + 1].d == -1 && p1 >= p2)
                {
                    if (i - 1 >= 0)
                    {
                        q.push(i - 1);
                    }
                    if (i + 1 < N)
                    {
                        q.push(i + 1);
                    }
                    per[i + 1].d = 0;
                    per[i + 1].p = per[i].p;
                }
            }
        }
 
        //나머지 사람이 만나지 않는 부분 정리
        for (int i = 0; i < N; i++)
        {
            if (per[i].d != 0)
            {
                per[i].p += per[i].d*T;
            }
        }
 
        vector<long long> x;
 
        for (int i = 0; i < Q; i++)
        {
            int tmp;
            cin >> tmp;
            x.push_back(per[tmp-1].p);
        }
 
        cout << "#" << t << " ";
        for (int i = 0; i < x.size(); i++)
        {
            cout << x[i] << " ";
        }
        cout << "\n";
 
 
    }
 
    return 0;
}