白駿11723号:集合


1.質問




2.例


all:1から20のすべての要素がセットSに追加されます.
check:checkを入力するたびに、要素が含まれている場合は1を出力し、そうでない場合は0を出力します.
※'&'演算の使用上の注意
a & (1 << b) //  연산 결과는 0 또는 (1<<b)가 나온다.
「&」演算子の結果は1または0ではなく、0または2番目のオペランドシフトのビットです.
したがって、if(a&(1<

3.解除


コレクションに要素が存在するかどうかを判断するだけで、ビットマスクが使用されます.
最大演算数が300000であるため、最初にタイムアウトが発生しました.
したがって,以下のようにcin,cout加速が必要である.
(※単一スレッドでのみ使用でき、printf、scanfとの混合はできません.)
	ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
最初は最後まで入力できない問題があり、allもemptyも追加の入力を受け入れなかったがcinが受信し、入力が中断した.
コード全体を以下に示します.
#include <iostream>
#include <string>

using namespace std;
int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int init_S = 0;

    cin >> n;

    while (n--)
    {
        int input;
        string command;
        cin >> command;

        if (command != "empty" && command != "all")
        {
            cin >> input;
        }

        if (command == "add")
        {
            init_S |= (1 << input);
        }
        else if (command == "check")
        {
            bool ans;

            if (init_S & (1 << input))
                ans = true;

            else
                ans = false;

            cout << ans << '\n';
        }
        else if (command == "remove")
        {
            init_S &= ~(1 << input);
        }
        else if (command == "toggle")
        {
            init_S ^= (1 << input);
        }
        else if (command == "all")
        {
            init_S = ((1 << 21) - 1);
        }
        else if (command == "empty")
        {
            init_S = 0;
        }
    }
}