Educational Codeforces Round 71 (Rated for Div. 2) E XOR Guessing (二进制分组，交互)

E. XOR Guessing

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

This is an interactive problem. Remember to flush your output while communicating with the testing program. You may use fflush(stdout) in C++, system.out.flush() in Java, stdout.flush() in Python or flush(output) in Pascal to flush the output. If you use some other programming language, consult its documentation. You may also refer to the guide on interactive problems: https://codeforces.com/blog/entry/45307.

The jury picked an integer x not less than 0 and not greater than 214−1. You have to guess this integer.

To do so, you may ask no more than 2 queries. Each query should consist of 100 integer numbers a1, a2, ..., a100 (each integer should be not less than 0 and not greater than 214−1). In response to your query, the jury will pick one integer i (1≤i≤100) and tell you the value of ai⊕x (the bitwise XOR of ai and x). There is an additional constraint on the queries: all 200 integers you use in the queries should be distinct.

It is guaranteed that the value of x is fixed beforehand in each test, but the choice of i in every query may depend on the integers you send.

Output

To give the answer, your program should print one line ! x with a line break in the end. After that, it should flush the output and terminate gracefully.

Interaction

Before giving the answer, you may submit no more than 2 queries. To ask a query, print one line in the following format: ? a1 a2 ... a100, where every aj should be an integer from the range [0,214−1]. The line should be ended with a line break character. After submitting a query, flush the output and read the answer to your query — the value of ai⊕x for some i∈[1,100]. No integer can be used in queries more than once.

If you submit an incorrect query (or ask more than 2 queries), the answer to it will be one integer −1. After receiving such an answer, your program should terminate immediately — otherwise you may receive verdict "Runtime error", "Time limit exceeded" or some other verdict instead of "Wrong answer".

Example

inputCopy

0

32

outputCopy

? 3 5 6

? 32 24 37

! 5

Note

The example of interaction is not correct — you should sumbit exactly 100 integers in each query. Everything else is correct.

Hacks are forbidden in this problem.

思路：

只看14位，第一个集合，后7为全放0，第二个集合，前7位放0，然后询问得到的答案，取第一个回复的后7位，第二个回复的前7位。。

什么200个数相互不同，例如第一个集合，后7位放0后，前7位随便取点不同的就好了。

细节见代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}

inline void getInt(int* p);

const int maxn = 1000010;

const int inf = 0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

std::vector<int> v;

void PRINF2(ll num, int k)

{

    for (int i = k; i >= 0; i--)

    {

        cout << (bool)(num & (1ll << i));

    }

    cout << endl;

}

int main()

{

    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);

    //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);

    int maxst = (1 << 8);

    int n = 100;

    v.clear();

    repd(i, 1, n)

    {

        int x = 0;

        x <<= 7;

        x += i;

        v.push_back(x);

    }

    cout << "?";

    for (auto x : v)

    {

        cout << " " << x;

    }

    cout << endl;

    int ans;

    cin >> ans;

    ans >>= 7;

    ans <<= 7;

    v.clear();

    repd(i, 1, n)

    {

        int x = 0;

        x += (i << 7);

        v.push_back(x);

        // PRINF2(x,25);

    }

    cout << "?";

    for (auto x : v)

    {

        cout << " " << x;

    }

    cout << endl;

    int y;

    cin >> y;

    for (int i = 6; i >= 0; --i)

    {

        if (y & (1 << i))

        {

            ans += (1 << i);

        }

    }

    cout << "! " << ans << endl;

    return 0;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    }

    else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}

巴特西

Educational Codeforces Round 71 (Rated for Div. 2) E XOR Guessing (二进制分组，交互)

最新文章

热门文章