CF835E The penguin’s game

The penguin’s game

题面翻译

交互题。

有一个序列,其中有恰好 2 个数是 y ,剩下的 n-2 个数是 x

你每次可以询问一个集合的异或和。

你需要用不超过 19 次询问找到两个为 y 的数的下标。

题目描述

Pay attention: this problem is interactive.

Penguin Xoriy came up with a new game recently. He has n icicles numbered from 1 to n . Each icicle has a temperature — an integer from 1 to 10^{9} . Exactly two of these icicles are special: their temperature is y , while a temperature of all the others is x≠y . You have to find those special icicles. You can choose a non-empty subset of icicles and ask the penguin what is the bitwise exclusive OR (XOR) of the temperatures of the icicles in this subset. Note that you can’t ask more than 19 questions.

You are to find the special icicles.

输入格式

The first line contains three integers n , x , y ( 2<=n<=1000 , 1<=x,y<=10^{9} , x≠y ) — the number of icicles, the temperature of non-special icicles and the temperature of the special icicles.

输出格式

To give your answer to the penguin you have to print character “!” (without quotes), then print two integers p_{1} , p_{2} ( p_{1}<p_{2} ) — the indexes of the special icicles in ascending order. Note that “!” and p_{1} should be separated by a space; the indexes should be separated by a space too. After you gave the answer your program should terminate immediately.

Interaction

To ask a question print character “?” (without quotes), an integer c ( 1<=c<=n ), and c distinct integers p_{1} , p_{2} , …, p_{c} ( 1<=p_{i}<=n ) — the indexes of icicles that you want to know about. Note that “?” and c should be separated by a space; the indexes should be separated by a space too.

After you asked the question, read a single integer — the answer.

Note that you can’t ask more than 19 questions. If you ask more than 19 questions or at least one incorrect question, your solution will get “Wrong answer”.

If at some moment your program reads -1 as an answer, it should immediately exit (for example, by calling exit(0)). You will get “Wrong answer” in this case, it means that you asked more than 19 questions, or asked an invalid question. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

Your solution will get “Idleness Limit Exceeded”, if you don’t print anything or forget to flush the output, including for the final answer .

To flush you can use (just after printing):

  • fflush(stdout) in C++;
  • System.out.flush() in Java;
  • stdout.flush() in Python;
  • flush(output) in Pascal;
  • For other languages see the documentation.

Hacking

For hacking use the following format:

n x y p_{1} p_{2}

Here 1<=p_{1}<p_{2}<=n are the indexes of the special icicles.

Contestant programs will not be able to see this input.

样例 #1

样例输入 #1

4 2 1
2
1
1

样例输出 #1

? 3 1 2 3
? 1 1
? 1 3
! 1 3

提示

The answer for the first question is

.

The answer for the second and the third questions is 1, therefore, special icicles are indexes 1 and 3.

You can read more about bitwise XOR operation here: https://en.wikipedia.org/wiki/Bitwise_operation#XOR.

#include <bits/stdc++.h>
#define int long long
using namespace std;
using cint = const int&;
constexpr int maxn = 1000001;
int opt;
int x, y, s[maxn], ans[maxn], siz, n, tmp, lgn, T;
inline int get() {
    cout << "? " << siz;
    for (int i = 1; i <= siz; ++i) cout << ' ' << s[i];
    cout << endl;
    cin >> opt;
    if (siz & 1) {
        return opt == (y);
    }
    else {
        return opt == (x ^ y);
    }
}
inline void make(cint k) {
    siz = 0;
    for (int i = 1; i <= n; ++i)
        if ((i >> k) & 1) s[++siz] = i;
}
inline int getxor() {
    int res = 0;
    for (int i = lgn; i >= 0; --i) {
        make(i);
        tmp = get();
        res <<= 1;
        res += tmp;
        if (tmp && !ans[0]) {
            ans[0] = siz;
            for (int i = 1; i <= siz; ++i) ans[i] = s[i];
        }
    }
    return res;
}
inline int gets() {
    int was = ans[0], res = 0;
    for (int i = 1; i <= siz; ++i) s[i] = ans[i];
    for (int i = log2(was); i >= 0; --i) {
        siz = res + (1ll << i);
        if (siz > was) continue;
        if (!get()) res = siz;
    }
    return ans[res + 1];
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> x >> y;
    lgn = log2(n);
    int sxor = getxor();
    int s1 = gets();
    int s2 = sxor ^ s1;
    cout << "! " << min(s1, s2) << ' ' << max(s1, s2) << endl;
}

  • # Tip

多测不清空,迟早见祖宗
算符优先级,括号最无敌

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇