Chocolate Bunny CodeForces

题意：

交互题

题目输入一个n，你需要输出一个满足要求的[1,n]的排列。

你可以最多询问2*n次来确定你要输出的排列·中每一个位置的值

每一次询问格式为“? a b”

它会回复你答案排列中第a个位置的元素取余于第b个位置的元素的值是多少

题解：

因为最后答案中每一个元素只会使用一次，那么你询问的va,vb肯定一个大一个小（v数组代表最后我们要输出的答案数组）

那么你用一个min(va,vb)%max(va,vb)==min(va,vb)

可以说两次询问可以确定一个元素的大小

那么就可以写代码了

代码：

int a[maxn];

void ask(int i,int j) {

    cout << "?" << " " << i << " " << j << endl;

    fflush(stdout);

}

int main() {

    int n;cin >> n;

    if(n == 1) {

        cout << "! 1" << endl;

        fflush(stdout);

        exit(0);

    }

    int id = 0;

    int x,y;

    ask(1,2);

    cin >> x;

    ask(2,1);

    cin >> y;

    if(x > y) {

        a[1] = x;

        id = 1;

    } else {

        a[2] = y;

        id = 2;

    }

    if(n == 2) {

        if(id == 1) cout << "! " << a[1] << " " << (3 - a[1]) << endl;

        else cout << "! " << (3 - a[2]) << " " << a[2] << endl;

        fflush(stdout);

        return 0;

    }

    if(id == 1) id = 2; else id = 1;

    for(int i = 3;i <= n;++i) {

        if(a[i] != 0) continue;

        x = 0,y = 0;

        ask(id,i);cin >> x;

        ask(i,id);cin >> y;

        if(x > y) {

            a[id] = x;

            id = i;

        } else {

            a[i] = y;

        }

    }

    a[id] = n;

    cout << "!";

    for(int i = 1;i <= n;++i) {

        cout << " " << a[i];

    }

    cout << endl;

    fflush(stdout);

    return 0;

}

巴特西

Chocolate Bunny CodeForces - 1407C 思维

最新文章

热门文章