abc313d, 1wa
  • 板块学术版
  • 楼主WillHou
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/8/11 00:07
  • 上次更新2023/11/3 04:35:14
查看原帖
abc313d, 1wa
533544
WillHou楼主2023/8/11 00:07

在大佬的帮助下,大部分数据都过了,还有一个点迷惑过不了。

#include <iostream>
const int N = 1009;
int n, k;
int ds[N << 1];
int res[N];
int seq[N];
int find(int x) { return ds[x]<0 ? x : (ds[x] = find(ds[x])); }
void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return ;
    if (ds[x] > ds[y]) std::swap(x, y);
    ds[x] += ds[y], ds[y] = x;
}
bool judge(int x, int y) { return find(x) == find(y); }
int main() {
    std::cin >> n >> k;
    for (int i = 1; i <= n << 1; i++)
        ds[i] = -1;
    for (int i = 1; i <= n; i++) {
        // printf("i = %d\n", i);
        std::cout << "?";
        for (int j = 1; j <= k; j++) {
            int t = i + j - 1;
            if (t > n) t -= n;
            std::cout << " " << t;
        }
        std::cout << std::endl;
        std::cin >> res[i];
        if (i == 1) continue;
        int x = i - 1, y = i + k - 1;
        if (y > n) y -= n;
        // printf("(x, y) = (%d, %d)\n", x, y);
        if (res[i-1] == res[i]) {
            merge(x, y);
            // puts("[merge]: (x, y)");
            merge(x + n, y + n);
            // puts("[merge]: (x+n, y+n)");
        } else {
            merge(x, y + n);
            // puts("[merge]: (x, y+n)");
            merge(x + n, y);
            // puts("[merge]: (x+n, y)");
        }
    }
    // puts("Ridiculous!");
    for (int i = 2; i <= n; i++)
        if (judge(1, i) == false)
            seq[i] = 1;
    int t = 0;
    for (int i = 1; i <= k; i++)
        t += seq[i];
    // if (res[1] != (t & 1)) t = 1;
    // else t = 0;
    if (res[1] != (t & 1)) {
        for (int i = 1; i <= n; i++)
            seq[i] = !seq[i];
    }
    std::cout << "!";
    for (int i = 1; i <= n; i++)
        std::cout << " " << seq[i];
    std::cout << std::endl;
    return 0;
}

https://atcoder.jp/contests/abc313/submissions/44442491

2023/8/11 00:07
加载中...