HIHO1236 【Scores】题解

 对于每个成绩,求出所有满足条件的人的编号,bitset合并即可
由于空间不够,所以要分一下块
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
int nmqnum;
bitset<50005s[10][2505], baseansAns;
struct node
{
    int id;
    int num;
    bool operator<(const node &bb)
    {
        return num < bb.num;
    }
a[10][50005];
int main()
{
    base[0] = 1;
    int T;
    scanf("%d", &T);
    while (T--)
    {
        num = 0;
        for (int i = 1i <= 5; ++i)
            s[i][0].reset();
        scanf("%d%d", &n, &m);
        for (int i = 1i <= n; ++i)
            for (int j = 1j <= 5; ++j)
            {
                a[j][i].id = i;
                scanf("%d", &a[j][i].num);
            }
        for (int i = 1i <= 5; ++i)
        {
            sort(a[i] + 1a[i] + n + 1);
            for (int j = 1j <= n; ++j)
            {
                if (j % 25 == 0 && j != 1)
                    s[i][j / 25= s[i][j / 25 - 1];
                s[i][j / 25][a[i][j].id] = 1;
            }
        }
        scanf("%d", &q);
        for (int i = 1i <= q; ++i)
        {
            Ans.set();
            for (int j = 1j <= 5; ++j)
            {
                ans.reset();
                int x;
                scanf("%d", &x);
                x ^= num;
                int l = 1r = n;
                while (l < r)
                {
                    int mid = (l + r + 1) >> 1;
                    if (a[j][mid].num <= x)
                        l = mid;
                    else
                        r = mid - 1;
                }
                if (l / 25 >= 1)
                    ans = s[j][l / 25 - 1];
                for (int k = l / 25 * 25k <= l; ++k)
                    ans[a[j][k].id] = 1;
                Ans &= ans;
            }
            num = Ans.count();
            printf("%d\n"num);
        }
    }
    return 0;
}

评论

此博客中的热门博文

min-max反演