글 읽기 - 예시 다 잘나오는데 1% 틀렷습니다..

worldbright 3년 전 0

(인덱스, 개수, 쓰레기타입)
이렇게 구현햇고
list에 대기열을,
set으로 소각장 만들어서 구현했는데요
예시 다 잘나오는데 왜 틀렸을가요 ㅠㅠ
#include <iostream>
#include <list>
#include <set>
#include <vector>
using namespace std;
typedef struct _data {
   int idx, n, type;
} Data;

void print(Data d) {
   cout << d.idx << " " << d.n << " " << d.type << endl;
}
int main()
{
   int tmp, n, m, k, q, o, l, r, i, p, q2, t, cnt = 1;
   int start = 0, end;
   list<Data> ai;
   list<int> second_order;

   auto compare = [](Data a, Data b) { return a.idx < b.idx; };
   set<Data, decltype(compare)> trash(compare);

   cin >> n >> m >> k >> q;
   end = m;

   for(int i = 0; i < n; i++)
   {
      cin >> tmp;
      if(ai.back().type == tmp) {
         ai.back().n++;
         continue;
      }
      Data d = {0, 1, tmp};
      ai.push_back(d);
   }
   for(int i = min(n,m); i > 0; i--)
   {
      Data &d = ai.front();
      d.idx = min(n,m) - i + 1;
      if(i > d.n) {
         i -= d.n - 1;
         trash.insert(d);
         ai.pop_front();
      }
      else if(i < d.n) {
         Data d2 = d;
         d.n -= i;
         d2.n = i;
         trash.insert(d2);
         break;
      } else {
         trash.insert(d);
         ai.pop_front();
         break;
      }
   }
   for(int j = 0; j < q; j++)
   {
      cin >> o;
      if(o == 1) {
         bool deletion = true;
         cin >> l >> r;
         Data ld = {l, 0, 0}, rd = {r, 0, 0};
         set<Data>::iterator low, high;
         if(!trash.empty()) {
            low = trash.upper_bound(ld);
            high = trash.upper_bound(rd);
            if(low != trash.begin()) --low;
            vector<Data> datas;
            if(low != trash.end() && (*low).idx + (*low).n -1 < l) low++;
            for(; low != high; low++) datas.push_back(*low);
            if(datas.size() == 1) {
               if(l <= datas[0].idx && datas[0].idx + datas[0].n <= r) {
                  trash.erase(datas[0]);
               } else if(l <= datas[0].idx) {
                  trash.erase(datas[0]);
                  datas[0].n -= r - datas[0].idx + 1;
                  datas[0].idx = r + 1;
                  trash.insert(datas[0]);
               } else if(datas[0].idx + datas[0].n - 1 <= r) {
                  trash.erase(datas[0]);
                  datas[0].n = l - datas[0].idx;
                  trash.insert(datas[0]);
               } else {
                  trash.erase(datas[0]);
                  Data data2 = datas[0];
                  datas[0].n = l - datas[0].idx;
                  data2.idx = r + 1;
                  data2.n -= r - datas[0].idx + 1;
                  trash.insert(datas[0]);
                  trash.insert(data2);
               }
            } else if(datas.size() > 1) {
               trash.erase(datas[0]);
               trash.erase(datas[datas.size()-1]);
               if(l != datas[0].idx) {
                  datas[0].n = l - datas[0].idx;
                  trash.insert(datas[0]);
               }
               if(r < datas[datas.size()-1].idx + datas[datas.size()-1].n - 1) {
                  datas[datas.size()-1].n -= r - datas[datas.size()-1].idx + 1;
                  datas[datas.size()-1].idx = r + 1;
                  trash.insert(datas[datas.size()-1]);
               }
               if(datas.size() >= 3) {
                  for(int i = 1; i < datas.size()-1; i++) trash.erase(datas[i]);
               }
            }
         }
         int remain = r-l+1, cur = l;
         if(ai.empty()) continue;
         Data *curD = &ai.front();
         while(remain > 0) {
            if(curD->n >= remain) {
               curD->n -= remain;
               Data d = {cur, remain, curD->type};

               trash.insert(d);
               if(curD->n == 0) ai.pop_front();
               break;
            } else {
               curD->idx = cur;
               trash.insert(*curD);
               cur += curD->n;
               remain -= curD->n;
               ai.pop_front();
               if(ai.empty()) break;
               curD = &ai.front();
            }
         }
      } else if(o == 2) {
         cin >> i;
         if(trash.empty()) {
            second_order.push_back(0);
            continue;
         }
         Data d = {i, 0, 0};
         set<Data>::iterator cur = trash.upper_bound(d);
         if(cur != trash.begin()) --cur;
         if((*cur).idx + (*cur).n - 1 < i || (*cur).idx > i) second_order.push_back(0);
         else second_order.push_back((*cur).type);
      } else if(o == 3) {
         cin >> p >> q2;
         Data d = {0, q2, p};
         ai.push_back(d);
      } else if(o == 4) {
         cin >> t;
         if(ai.empty()) continue;
         Data *curD = &ai.front();
         while(t > 0) {
            if(curD->n >= t) {
               curD->n -= t;
               if(curD->n == 0) ai.pop_front();
               break;
            } else {
               t -= curD->n;
               ai.pop_front();
               curD = &ai.front();
            }
         }
      }
   }
   
   while(!second_order.empty()) {
      cout << second_order.front() << " ";
      second_order.pop_front();
   }

   cout << endl;
   for(set<Data>::iterator iter = trash.begin(); iter != trash.end(); iter++) {
      if((*iter).idx != cnt) {
         for(; cnt < (*iter).idx; cnt++) cout << 0 << " ";
      }
      for(int i = 0; (i < (*iter).n) && (cnt <= m); i++, cnt++) {
         cout << (*iter).type << " ";
      }
   }
   for(int i = cnt; i <= m; i++) {
      cout << 0 << " ";
   }
   cout << endl;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

예시 다 잘나오는데 1% 틀렷습니다..

worldbright 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
