201709-2

시험 문제 번호: 201709 - 2 시험 문제 이름: 공공 열쇠 함 시간 제한: 1.0s 메모리 제한: 256.0MB 문제 설명: 문제 설명 은 한 학교의 선생님 이 N 개의 교실 을 공유 하고 규정 에 따라 모든 열 쇠 는 공공 열쇠 함 에 넣 어야 하 며 선생님 은 열 쇠 를 가지 고 집에 갈 수 없습니다.선생님 은 수업 전 마다 공공 열쇠 함 에서 자신 이 수업 하 는 교실 열 쇠 를 찾 아 문 을 열 고 수업 을 마 친 뒤 열 쇠 를 열쇠 함 에 다시 넣 었 다.열쇠 상 자 는 모두 N 개의 고리 가 있 는데 왼쪽 에서 오른쪽으로 한 줄 로 서서 N 개의 교실 열 쇠 를 걸 수 있다.열쇠 꾸러미 는 고정된 매달 린 위치 가 없 지만 열쇠 에 표지 가 있어 선생님 들 이 열 쇠 를 헷 갈 리 지 않 는 다.열 쇠 를 찾 을 때마다 선생님 들 은 자신 이 필요 로 하 는 열 쇠 를 찾 아 다른 열 쇠 를 옮 기지 않 고 가 져 간다.열 쇠 를 돌려 줄 때마다 열 쇠 를 돌려 주 는 선생님 은 맨 왼쪽 에 있 는 빈 고 리 를 찾 아 열 쇠 를 이 고리 에 걸 었 다.만약 여러 명의 선생님 이 열 쇠 를 돌려 준다 면, 그들 은 열쇠 번호 에 따라 어 릴 때 부터 큰 순서 로 돌려 준다.같은 시각 에 선생님 도 있 고 열쇠 도 있 고 선생님 도 있 으 면 선생님 들 은 먼저 열 쇠 를 다 돌려 주 고 꺼 낼 것 이다.오늘부터 열 쇠 는 번호 에 따라 어 릴 때 부터 큰 순서 로 열쇠 상자 에 넣 었 다.K 명의 선생님 이 수업 을 하려 고 하 는데 모든 선생님 이 필요 로 하 는 열 쇠 를 주 고 수업 을 시작 하 는 시간 과 수업 시간 이 길다 고 가정 합 니 다. 수업 이 끝 나 는 시간 이 바로 열 쇠 를 돌려 주 는 시간 이 라 고 가정 합 니 다. 최종 열쇠 상자 안의 열 쇠 는 순서 가 어떻게 됩 니까?입력 형식 입력 의 첫 줄 에는 두 개의 정수 N, K 가 포함 되 어 있 습 니 다.그 다음 에 K 줄 은 각 줄 에 세 개의 정수 w, s, c 로 한 선생님 이 사용 해 야 할 열쇠 번호, 수업 을 시작 하 는 시간 과 수업 시간 을 나타 낸다.같은 열 쇠 를 사용 하 는 선생님 이 많 을 지 모 르 지만 선생님 이 열 쇠 를 사용 하 는 시간 은 겹 치지 않 는 다.입력 데이터 가 입력 형식 에 만족 하도록 보장 합 니 다. 데이터 의 합 법성 을 검사 할 필요 가 없습니다.출력 형식 은 한 줄 을 출력 합 니 다. N 개의 정 수 를 포함 하고 인접 한 정수 간 에 하나의 빈 칸 으로 구분 되 며 각 갈고리 에 걸 려 있 는 열쇠 번 호 를 순서대로 표시 합 니 다.샘플 입력 5243 3227 샘플 출력 143325 샘플 은 첫 번 째 선생님 이 시각 3 부터 4 번 교실 열 쇠 를 사용 하고 3 단위 시간 을 사용 하기 때문에 시간 6 시 에 열 쇠 를 돌려 준 다 는 것 을 설명 한다.두 번 째 선생님 은 시각 2 부터 열 쇠 를 사용 하고 7 단위 의 시간 을 사용 하기 때문에 시각 9 시 에 열 쇠 를 돌려 줍 니 다.각 중요 한 시간 후의 열쇠 상 태 는 다음 과 같다 (X 는 비어 있다). 시간 2 후 는 1X 345 이다.시각 3 후 1X3X 5;시각 6 후 143 X5;시각 9 후 는 14325 이다.샘플 입력 5 7 1 14 3 12 1 15 12 7 18 12 21 19 5 30 9 샘플 출력 1 23 5 4 평가 사례 규모 와 약정 30% 에 대한 평가 사례, 1 ≤ N, K ≤ 10, 1 ≤ w ≤ N, 1 ≤ s, c ≤ 30;60% 의 평가 용례 에 대해 1 ≤ N, K ≤ 50, 1 ≤ w ≤ N, 1 ≤ s ≤ 300, 1 ≤ c ≤ 50;모든 평가 용례 에 대하 여 1 ≤ N, K ≤ 1000, 1 ≤ w ≤ N, 1 ≤ s ≤ 10000, 1 ≤ c ≤ 100.

#include
#include
#include
using namespace std;

struct Teacher{
    int x;//0     1    
    int id;
    int time;
};
bool cmp(Teacher a,Teacher b)
{
    if(a.timereturn true;
    }else if(a.time == b.time)
    {
        if(a.xreturn true;
        }
        else if(a.x==b.x)
        {
            return a.idelse return false;
    }else   
        return false;   
}
int main()
{
    int n,k;
    cin >> n >> k;
    vector v;
    vector<int> p_k(n+1,0),k_p(n+1,0);
    //                 
    vector<int> q;
    //     
    int w,s,c;
    for(int i = 1; i <= n; i++)
    {
        p_k[i] = i;
        k_p[i] = i;
    } 
    for(int i = 0; i < k; i++)
    {
        cin >> w >> s >> c;
        Teacher temp1,temp2;
        temp1.x = 1;
        temp1.id = w;
        temp1.time = s;
        temp2.x = 0;
        temp2.id = w;
        temp2.time = s+c;
        v.push_back(temp1);
        v.push_back(temp2);
    }
    //       
    sort(v.begin(),v.end(),cmp);
//  for(int i = 0; i < v.size(); i++)
//  {
//      cout << v[i].id <
//  }
    for(int i = 0; i < 2*k; i++)
    {
        if(v[i].x==1)
        {
            p_k[k_p[v[i].id]] = 0;      
            q.push_back(k_p[v[i].id]);
            //       
            sort(q.begin(),q.end());
            k_p[v[i].id] = 0;
//          for(int k = 1; k <= n; k++)
//          {
//              if(p_k[k])
//              cout << p_k[k]<
//              else
//              cout << "# ";
//          }
//          cout << endl;
        }
        else
        {
            p_k[q.front()] = v[i].id;
            k_p[v[i].id] = q.front();
            q.erase(q.begin());
//          for(int k = 1; k <= n; k++)
//          {
//              if(p_k[k])
//              cout << p_k[k]<
//              else
//              cout << "# ";
//          }
//          cout << endl;
        }
    }
    for(int i = 1; i < n; i++)
    {
        cout << p_k[i] << " ";
    }
    cout << p_k[n] << endl;
    return 0;
}