メモ

自分に向けて書いたメモを取り扱っています.

AOJ 0536 Shuffle

汚い

ソースコード

typedef pair<int, int> P;

int main()
{
    int n, m, p, q, r, x, y;

    while(cin >> n, n)
    {
        vector<P> cards;
        cards.push_back(make_pair(1, n));

        cin >> m >> p >> q >> r;
        while(m--)
        {
            // flag : 0 => Left, 1 => Middle, 2 => Right
            int flag = 0;

            vector<P> Left, Middle, Right;

            cin >> x >> y;

            int diff = y - x;

            for(int i = 0, point = 0; i < cards.size(); i++)
            {
                int left = cards[i].first;
                int right = cards[i].second;

                int len = right - left + 1;

                // どっちも範囲に入っている時
                if(point < x && x <= point + len && point <= y && y <= point + len)
                {
                    Left.push_back(make_pair(left, left + (x - point) - 1));
                    Middle.push_back(make_pair(left + (x - point), left + (y - point) - 1));
                    Right.push_back(make_pair(left + (y - point), right));
                    flag = 2;
                }
                // 左だけ
                else if(point < x && x <= point + len)
                {
                    Left.push_back(make_pair(left, left + (x - point) - 1));
                    Middle.push_back(make_pair(left + (x - point), right));
                    flag = 1;
                }
                // 右だけ
                else if(point < y && y <= point + len)
                {
                    Middle.push_back(make_pair(left, left + (y - point) - 1));
                    Right.push_back(make_pair(left + (y - point), right));
                    flag = 2;
                }
                // 入っていないとき
                else
                    if(flag == 0)
                        Left.push_back(cards[i]);
                    else if(flag == 1)
                        Middle.push_back(cards[i]);
                    else
                        Right.push_back(cards[i]);

                point += len;
            }
            cards.clear();

            for(int i = 0; i < Right.size(); i++)
                if(Right[i].first <= Right[i].second)
                    cards.push_back(Right[i]);
            
            for(int i = 0; i < Middle.size(); i++)
                if(Middle[i].first <= Middle[i].second)
                    cards.push_back(Middle[i]);
            
            for(int i = 0; i < Left.size(); i++)
                if(Left[i].first <= Left[i].second)
                    cards.push_back(Left[i]);
            
        }

        int res = 0;
        int point = 0;
        bool flag = false;

        for(int i = 0; i < cards.size(); i++)
        {
            int left = cards[i].first;
            int right = cards[i].second;
            int len = right - left + 1;

            if(point < p && p <= point + len && point <= q && q <= point + len)
            {
                for(int i = left + (p - point) - 1; i <= left + (q - point) - 1 && r <= i; i++)
                    res++;
                break;
            }

            else if(point < p && p <= point + len)
            {
                for(int i = left + (p - point) - 1; i <= right && i <= r; i++)
                    res++;
                flag = true;
            }
            else if(point < q && q <= point + len)
            {
                for(int i = left; i <= left + (q - point) - 1 && i <= r; i++)
                    res++;
                break;
            }
            else if(flag)
            {
                for(int i = left; i <= right && i <= r; i++)
                    res++;
            }

            point += len;
        }

        cout << res << endl;
    }
}