Rezhou
登出
QOJ.ac
QOJ
比赛
Category
题库
提交记录
Hack!
博客
PKUTS
搜索题库
ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#656945	#7900. Gifts from Knowledge	Rezhou	WA	7ms	3664kb	C++23	5.2kb	2024 - 10 - 19 13:54 : 50	2024 - 10 - 19 13 : 54 : 50
Judging History
你现在查看的是最新测评结果

[2024 - 10 - 19 13:54 : 50]评测
测评结果：WA用时：7ms内存：3664kb
查看
[2024 - 10 - 19 13:54 : 50]提交
answer
#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
#define double long double

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef const double* (*p_fun)(const double*, int);
const LL N = 1e5 + 10, M = 5e3 + 10, mod = 1e9 + 7, LLF = 1e13, null = 0x3f3f3f3f3f3f3f;

template <typename T> bool chmax(T& a, const T& b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T, typename... Args> bool chmax(T& a, const T& b, const Args &...args)
{
    bool updated = chmax(a, b);
    return chmax(a, args...) || updated;
}
template <typename T> bool chmin(T& a, const T& b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T, typename... Args> bool chmin(T& a, const T& b, const Args &...args)
{
    bool updated = chmin(a, b);
    return chmin(a, args...) || updated;
}
class UnionFind
{
public:
    vector<int> parent;
    vector<int> size;
    int n;
    // 当前连通分量数目
    int setCount;

public:
    UnionFind(int _n) : n(_n), setCount(_n), parent(_n), size(_n, 1)
    {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x)
    {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }

    bool merge(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        if (size[x] < size[y])
            swap(x, y);
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }

    bool connected(int x, int y)
    {
        x = find(x);
        y = find(y);
        return x == y;
    }
};
int qmi(int a, int b)
{
    int res = 1;
    a %= mod;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }

    return res;
}
int sqrt(int x)
{
    int l = 0, r = 3e9; // LLONG_MAX
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (mid * mid > x)
            r = mid - 1; // 向下取整
        else
            l = mid;
    }
    return r;
}

int get(int x)
{
    int res = 0;
    while (x)
    {
        chmax(res, x % 10);
        x /= 10;
    }
    return res;
}

bool check(vector<char>& v)
{
    int mid = v.size() / 2;
    if (v.back() != v.front())
        return 0;

    int l = 1, r = v.size() - 2;
    while (l < r)
    {
        if (v[l] == v[l - 1] || v[l] != v[r])
            return 0;
        l++, r--;
    }
    return 1;
}

int p[N], d[N];

int find(int x)
{
    if (p[x] != x)
    {
        int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }

    return p[x];
}
static inline void solve()
{
    int c, r;
    cin >> c >> r;

    vector<string> v(c + 1);
    for (int i = 1; i <= c; i++)
        p[i] = i, d[i] = 0;
    for (int i = 1; i <= c; i++)
        cin >> v[i];
    vector<int> lock(r);
    vector<vector<pii>> f(r);

    bool flag = 0;
    for (int i = 0; i < r; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            bool flag1 = 0, flag2 = 0;
            if (v[j][i] == '1')
            {
                flag1 = 1;
                if (f[i].size())
                {
                    for (auto [y, op] : f[i])
                    {
                        int x = j;
                        op++;
                        op %= 2;
                        int px = find(x), py = find(y);
                        if (px == py && ((d[x] - d[y]) % 2 + 2) % 2 != op)
                            flag = 1;
                        else if (px != py)
                        {
                            p[px] = py;
                            d[px] = ((d[y] - d[x] + op) % 2 + 2) % 2;
                        }
                    }
                }
            }
            if (v[j][r - i - 1] == '1')
            {
                flag2 = 1;
                if (f[i].size())
                {
                    for (auto [y, op] : f[i])
                    {
                        int x = j;
                        int px = find(x), py = find(y);
                        if (px == py && ((d[x] - d[y]) % 2 + 2) % 2 != op)
                            flag = 1;
                        else if (px != py)
                        {
                            p[px] = py;
                            d[px] = ((d[y] - d[x] + op) % 2 + 2) % 2;
                        }
                    }
                }
            }
            if (flag1)
                f[i].push_back({ j, 0 });
            if (flag2)
                f[i].push_back({ j, 1 });
        }
    }

    vector<int> vis(c + 1);
    int ans = 0;

    for (int i = 1; i <= c; i++)
    {
        int x = find(i);
        if (!vis[x])
            vis[x] = 1, ans++;
    }
    if (flag)
    {
        cout << 0 << "\n";
        return;
    }
    cout << qmi(2, ans) << "\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cout << unitbuf;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

answer.code:14:9: error: "#" is not a valid filename
   14 | #656945 #7900. Gifts from Knowledge     Rezhou  WA      7ms     3664kb  C++23   5.2kb   2024 - 10 - 19 13:54 : 50       2024 - 10 - 19 13 : 54 : 50
      |         ^
answer.code:1:1: error: ‘Rezhou’ does not name a type
    1 | Rezhou
      | ^~~~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:62,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:23:
/usr/include/c++/13/ext/type_traits.h:164:35: error: ‘constexpr const bool __gnu_cxx::__is_null_pointer’ redeclared as different kind of entity
  164 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/13/ext/type_traits.h:159:5: note: previous declaration ‘template<class _Type> constexpr bool __gnu_cxx::__is_null_pointer(_Type)’
  159 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/13/ext/type_traits.h:164:26: error: ‘nullptr_t’ is not a member of ‘std’; did you mean ‘nullptr_t’?
  164 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/13/cstddef:50,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:41:
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:443:29: note: ‘nullptr_t’ declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
In file included from /usr/include/c++/13/bits/stl_pair.h:60,
                 from /usr/include/c++/13/bits/stl_algobase.h:64:
/usr/include/c++/13/type_traits:510:26: error: ‘std::size_t’ has not been declared
  510 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/13/type_traits:511:25: error: ‘_Size’ was not declared in this scope
  511 |     struct is_array<_Tp[_Size]>
      |                         ^~~~~
/usr/include/c++/13/type_traits:511:31: error: template argument 1 is invalid
  511 |     struct is_array<_Tp[_Size]>
      |                               ^
/usr/include/c++/13/type_traits:617:33: error: ‘nullptr_t’ is not a member of ‘std’; did you mean ‘nullptr_t’?
  617 |     struct is_null_pointer<std::nullptr_t>
      |                                 ^~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:443:29: note: ‘nullptr_t’ declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
/usr/include/c++/13/type_traits:617:42: error: template argument 1 is invalid
  617 |     struct is_null_pointer<std::nullptr_t>
      |                                          ^
/usr/include/c++/13/type_traits:621:48: error: template argument 1 is invalid
  621 |     struct is_null_pointer<const std::nullptr_t>
      |                                                ^
/usr/include/c++/13/type_traits:625:51: error: template argument 1 is invalid
  625 |     struct is_null_pointer<volatile std::nullptr_t>
      |                                                   ^
/usr/include/c++/13/type_traits:629:57: error: template argument 1 is invalid
  629 |     struct is_null_pointer<const volatile std::nullptr_t>
      |                                                         ^
/usr/include/c++/13/type_traits:1348:37: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
 1348 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/type_traits:1348:57: error: template argument 1 is invalid
 1348 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/13/type_traits:1357:37: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
 1357 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/type_traits:1357:46: error: template argument 1 is invalid
 1357 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/13/type_traits:1359:26: error: ‘std::size_t’ has not been declared
 1359 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/13/type_traits:1360:21: error: ‘_Size’ was not declared in this scope
 1360 |     struct rank<_Tp[_Size]>
      |                     ^~~~~
/usr/include/c++/13/type_traits:1360:27: error: template argument 1 is invalid
 1360 |     struct rank<_Tp[_Size]>
      |                           ^
/usr/include/c++/13/type_traits:1361:37: ...