59pts求调
查看原帖
59pts求调
1307516
__asdf__楼主2025/1/8 21:21
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define N 25

// #define DEBUG 1  // 调试开关
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
    IO() : p1(buf), p2(buf), pp(pbuf) {}

    ~IO()
    {
        fwrite(pbuf, 1, pp - pbuf, stdout);
    }
#endif
    char gc()
    {
#if DEBUG  // 调试,可显示字符
        return getchar();
#endif
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
        return p1 == p2 ? ' ' : *p1++;
    }

    bool blank(char ch)
    {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }

    template <class T>
    void read(T &x)
    {
        double tmp = 1;
        bool sign = false;
        x = 0;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
        if (ch == '.')
            for (ch = gc(); isdigit(ch); ch = gc())
                tmp /= 10.0, x += tmp * (ch - '0');
        if (sign) x = -x;
    }

    void read(char *s)
    {
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
    }

    void read(char &c)
    {
        for (c = gc(); blank(c); c = gc());
    }

    void push(const char &c)
    {
#if DEBUG  // 调试,可显示字符
        putchar(c);
#else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
#endif
    }

    template <class T>
    void write(T x)
    {
        if (x < 0) x = -x, push('-');  // 负数输出
        static T sta[35];
        T top = 0;
        do
        {
            sta[top++] = x % 10, x /= 10;
        }
        while (x);
        while (top) push(sta[--top] + '0');
    }

    template <class T>
    void write(T x, char lastChar)
    {
        write(x), push(lastChar);
    }
} io;

int h, w;
int g[N][N];
int column[N];
int sum;

#define M 1000010

int ans1[M];
int ans2[M];
pair<int, int> ans[N << 1];
unordered_map<int, int> mp1;
unordered_map<int, int> mp2;

signed main()
{
    io.read(h);
    io.read(w);
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            io.read(g[i][j]);
        }
    }
    io.read(sum);
    for (int s = 0; s < (1 << h); s++)
    {
#define row_state s
        mp1.clear();
        mp2.clear();
        for (int i = 1; i <= w; i++)
        {
            column[i] = 0;
        }
        for (int i = 1; i <= h; i++)
        {
            if (!(row_state & (1 << (i - 1))))
            {
                for (int j = 1; j <= w; j++)
                {
                    column[j] += g[i][j];
                }
            }
        }
        // 从column中找一些数和为sum
        int len1 = w / 2;
        int len2 = w - len1;
        int n = 0;
        int m = 0;
        for (int s = 0; s < (1 << len1); s++)
        {
            int res = 0;
            for (int i = 1; i <= len1; i++)
            {
                if (s & (1 << (i - 1)))
                {
                    res += column[i];
                }
            }
            mp1[res] = s;
            ans1[n++] = res;
        }
        for (int s = 0; s < (1 << len2); s++)
        {
            int res = 0;
            for (int i = 1; i <= len2; i++)
            {
                if (s & (1 << (i - 1)))
                {
                    res += column[i + len1];
                }
            }
            mp2[res] = s;
            ans2[m++] = res;
        }
        sort(ans1, ans1 + n);
        sort(ans2, ans2 + m);
        int j = m - 1;
        for (int i = 0; i < n; i++)
        {
            while (j > 0 && ans1[i] + ans2[j] > sum)
            {
                j--;
            }
            if (ans1[i] + ans2[j] == sum)
            {
                int cnt = 0;
                for (int k = 1; k <= h; k++)
                {
                    if (row_state & (1 << (k - 1)))
                    {
                        ans[++cnt] = make_pair(1, k);
                    }
                }
                for (int k = 1; k <= len1; k++)
                {
                    if (!(mp1[ans1[i]] & (1 << (k - 1))))
                    {
                        ans[++cnt] = make_pair(2, k);
                    }
                }
                for (int k = 1; k <= len2; k++)
                {
                    if (!(mp2[ans2[j]] & (1 << (k - 1))))
                    {
                        ans[++cnt] = make_pair(2, k + len1);
                    }
                }
                io.push('Y');
                io.push('E');
                io.push('S');
                io.push('\n');
                io.write(cnt, '\n');
                for (int i = 1; i <= cnt; i++)
                {
                    io.write(ans[i].first, ' ');
                    io.write(ans[i].second, '\n');
                }
                exit(0);
            }
        }
#undef row_state
    }
    io.push('N');
    io.push('O');
    io.push('\n');
    return 0;
}
2025/1/8 21:21
加载中...