子任务1

注意到只有四个数。

可以先通过一次操作二找出 (3,4) 的位置和 (1,2) 的位置。

然后再分别用四次操作一，让 (3,4) 来对 (1,2) 取模确定四个位置。

int n = 读取(); int m1 = 读取(); int m2 = 读取(); int m3 = 读取();
if (n == 4) {
    printf("? 4 1 2 3 4 3\n"); fflush(stdout);
    int k = 读取(); int a = 读取(); int b = 读取();
    for (int i = 1; i <= 4; i++) {
        if (i != a && i != b) {
            if (!c) c = i;
            else d = i;
        }
    }
    printf("! %d %d\n", a, c); fflush(stdout); int ans1 = 读取();
    printf("! %d %d\n", a, d); fflush(stdout); int ans2 = 读取();
    if (ans1 + ans2 == 0) {
        ed[b] = 3; ed[a] = 4;
    } else {
        ed[b] = 4; ed[a] = 3;
        if (ans1) {
            ed[c] = 2; ed[d] = 1;
        } else {
            ed[d] = 2; ed[c] = 1;
        }
        printf("A %d %d %d %d\n", ed[1], ed[2], ed[3], ed[4]);
        fflush(stdout); return 0;
    }
    printf("! %d %d\n", b, c); fflush(stdout); int ans3 = 读取();
    printf("! %d %d\n", b, d); fflush(stdout); int ans4 = 读取();
    if (ans3) {
        ed[c] = 2; ed[d] = 1;
    } else {
        ed[c] = 1; ed[d] = 2;
    }
    printf("A %d %d %d %d\n", ed[1], ed[2], ed[3], ed[4]);
    fflush(stdout); return 0;
}

子任务2

发现 (m_2 = n)，且 (m_3) 是 (m_2^2)。

那么我们可以通过 (n) 次询问来确定每个数的位置。

每次询问 (n) 个数，询问的上界减一，然后找出给的数中没有被确定位置的数即可。

int n = 读取(); int m1 = 读取(); int m2 = 读取(); int m3 = 读取();
if (n == 500) {
    for (int i = n; i >= 1; i--) {
        printf("? %d ", i);
        for (int j = 1; j <= n; j++)
            if (!标记[j]) printf("%d ", j);
        printf("%d\n", i); fflush(stdout);
        int x = 读取(); int y = 读取(); ed[y] = i; 标记[y] = 1;
    }
    printf("A ");
    for (int i = 1; i <= n; i++) printf("%d ", ed[i]);
    fflush(stdout); return 0;
}

子任务3~6

观察到 (m_1) 很大，(m_2) 很小，但 (2^{17} > 5 \times 10^4)。

这启发我们可以用类似倍增的做法来处理。

可以发现，((\lceil \frac{n}{2} \rceil, n]) 中的每个数对 (\lceil \frac{n}{2} \rceil) 取模都可以得到不同的结果。

所以，如果我们知道了 ([1, \lceil \frac{n}{2} \rceil]) 中每个数的位置，那么剩下的数位置可以通过不断进行操作一来确定。

想要确定 ([1, \lceil \frac{n}{2} \rceil])，可以转化为知道了 ([1, \lceil \frac{n}{4} \rceil]) 来用同样的方法求 ((\lceil \frac{n}{4} \rceil, \lceil \frac{n}{2} \rceil]) 得到。

所以我们可以通过递归分治的方式来处理。

我们在数轴上找出每个长为 (n \times \frac{1}{2^i}) 的段，然后处理这一段内的数的位置即可。

void 工作(int 左, int 右, int 计数) {
    int 中间 = (右 + 1) / 2 + 1; 全部 = 0;
    if (左 == 右) {
        for (int i = 1; i <= n; i++)
            if (!位置[i]) 位置[i] = 计数;
        return;
    }
    for (int i = 1; i <= n; i++)
        if (!位置[i]) 队列[++全部] = i;
    printf("? %d ", 全部);
    for (int i = 1; i <= 全部; i++) printf("%d ", 队列[i]);
    printf("%d\n", 中间); fflush(stdout);
    int x = 读取();
    for (int i = 1; i <= x; i++) 位置[读取()] = 计数;
    工作(左, 中间 - 1, 计数 + 1);
}
// 下面是主函数内的部分
int n = 读取(); int m1 = 读取(); int m2 = 读取(); int m3 = 读取();
if (m2 >= 17) {
    for (int i = 1; i <= n; i++) 数组[i] = i;
    工作(1, n, 1);
    排序(数组 + 1, 数组 + n + 1, 比较器);
    ed[数组[1]] = 1; ed[数组[2]] = 2; int 最大值, id = 数组[2];
    for (int i = 3; i <= n; i++) {
        if (位置[数组[i]] != 位置[数组[i - 1]]) {
            lst = id; 最大值 = id; id = 0;
        }
        printf("! %d %d\n", 数组[i], lst); fflush(stdout);
        int x;
        ed[数组[i]] = ed[lst] + (x = 读取());
        if (!x) ed[数组[i]] = (ed[lst] << 1);
        if (最大值 < ed[数组[i]]) 最大值 = ed[数组[i]], id = 数组[i];
    }
    printf("A");
    for (int i = 1; i <= n; i++) printf(" %d", ed[i]);
    fflush(stdout); return 0;
}

子任务7

可以发现对于最后一组数据，(2^{15} \leq 5 \times 10^4 < 2^{16})。也就是说我们操作二理论上多进行了一次。

想办法怎么减少次数。

我们发现递归的时候是最后剩余了一个 (1) 然后退出的。此时我们可以找出 (1,2,3,4) 的位置。

如果我们不用操作二找出最后一个 (1) 的位置，而是采用子任务1的方法来的话，理论上就可以使操作二控制在一个可行的范围内了。

然后我们在子任务3~6的代码上套一个子任务1的代码就可以通过这个测试点。

void 工作2(int 左, int 右, int 计数) {
    int 中间 = (右 + 1) / 2 + 1; 全部 = 0;
    if (中间 == 2) {
        for (int i = 1; i <= n; i++)
            if (!位置[i]) 位置[i] = 计数;
        return;
    }
    for (int i = 1; i <= n; i++)
        if (!位置[i]) 队列[++全部] = i;
    printf("? %d ", 全部);
    for (int i = 1; i <= 全部; i++) printf("%d ", 队列[i]);
    printf("%d\n", 中间); fflush(stdout);
    int x = 读取();
    for (int i = 1; i <= x; i++) 位置[读取()] = 计数;
    工作2(左, 中间 - 1, 计数 + 1);
}
// 下面是主函数内的部分
for (int i = 1; i <= n; i++) 数组[i] = i;
工作2(1, n, 1);
排序(数组 + 1, 数组 + n + 1, 比较器);

int c = 数组[2], d = 数组[1], a = 数组[3], b = 数组[4];
printf("! %d %d\n", a, c); fflush(stdout); int ans1 = 读取();
printf("! %d %d\n", a, d); fflush(stdout); int ans2 = 读取();
if (ans1 + ans2 != 0) {
    ed[a] = 3; ed[b] = 4;
    if (ans1) {
        ed[c] = 2; ed[d] = 1;
    } else {
        ed[d] = 2; ed[c] = 1;
    }
} else {
    ed[a] = 4; ed[b] = 3;
    printf("! %d %d\n", b, c); fflush(stdout); int ans3 = 读取();
    printf("! %d %d\n", b, d); fflush(stdout); int ans4 = 读取();
    if (ans3) {
        ed[c] = 2; ed[d] = 1;
    } else {
        ed[c] = 1; ed[d] = 2;
    }
}

int 最大值, id;
if (ed[数组[3]] == 4) id = 数组[3];
else id = 数组[4];
for (int i = 5; i <= n; i++) {
    if (位置[数组[i]] != 位置[数组[i - 1]]) {
        lst = id; 最大值 = id; id = 0;
    }
    printf("! %d %d\n", 数组[i], lst); fflush(stdout);
    int x;
    ed[数组[i]] = ed[lst] + (x = 读取());
    if (!x) ed[数组[i]] = (ed[lst] << 1);
    if (最大值 < ed[数组[i]]) 最大值 = ed[数组[i]], id = 数组[i];
}
printf("A");
for (int i = 1; i <= n; i++) printf(" %d", ed[i]);
fflush(stdout); return 0;

但这份代码又不能通过子任务3~4，因为在前面的小数据递归时，按 (n \times \frac{1}{2^i}) 大小分的块可能使得 (3,4) 不在同一块中而 (4,5) 在同一块中，所以找完 (1) 到 (4) 的位置后再处理后面时 (5) 不会被处理到。

这里特判一下 (3,4) 是不是在一块就可以了。

但是我是个懒人，所以我把上面所有的代码全拼起来了。

然后我就过了。