当前位置：首页 > news >正文

打卡信奥刷题（3224）用C++实现信奥题 P8320 『JROI-4』Sunset

news 2026/5/7 23:11:08

P8320 『JROI-4』Sunset

题目背景

写不出优美的文字，索性不放背景了。【背景待填充】

由于这只是个 C，出题人打算良心点，于是加了几个0 00（指交互次数）（确信）——验题人注。

题目描述

这是一道交互题。

落日可以抽象成一个序列{ a n } \{a_n\}{an}.

{ a n } \{a_n\}{an}是一个1 ∼ n 1\sim n1∼n的排列。

你还有一个数列{ d n } \{d_n\}{dn}，为当前a aa数列的前缀最大值。

换言之，
d i = max ⁡ j = 1 i { a j } d_i=\max_{j=1}^i \{a_j\}di=j=1maxi{aj}

注意：根据前文的定义，{ d n } \{d_n\}{dn}可能随着{ a n } \{a_n\}{an}数列的改变而改变。

您可以进行两种不同的操作：

指定一个i ii，询问对于当前的a aa数列，d 1 ∼ i d_{1\sim i}d1∼i中有几个不同的值。
指定一个i ii，使得a i ← 0 a_i\leftarrow 0ai←0.

请使用不超过5500 55005500次操作求出原排列。

保证交互库是静态的，即交互库不会在交互过程中改变a aa数列。

输入格式

本题多测，第一行一个整数T TT，表示测试组数，接下来T TT行每行一个整数n nn，表示本组数据下数列的长度。

本题使用 IO 交互模式。

交互格式

? 1 i询问d 1 ∼ i d_{1\sim i}d1∼i中有几个不同的值，交互库会返回一个正整数x xx表示答案。
? 2 i使a i = 0 a_i=0ai=0。
! a1 a2 a3 ... an输出答案。

请注意：在每组数据中，请保证前两种操作的次数总和不超过5500 55005500。

需要注意的是，在每一次操作后，需要调用以下函数刷新缓存：

对于 C/C++：fflush(stdout);
对于 C++：std::cout << std::flush;
对于 Java：System.out.flush();
对于 Python：stdout.flush();
对于 Pascal：flush(output);

对于其他语言，请自行查阅对应语言的帮助文档。

输出格式

见「交互格式」。

输入输出样例 #1

输入 #1

1 3 1 2 3 2

输出 #1

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

说明/提示

样例仅供理解交互过程，可能不符合逻辑。

【样例解释】

初始的序列a aa为1 2 3，d dd为1 2 3.

在对交互库输出了形如? 2 2的命令后，序列a aa变为1 0 3，d dd变为1 1 3，此时d 1 ∼ d 3 d_1\sim d_3d1∼d3中有2 22种不同的值，分别是1 , 3 1,31,3.

可供选手参考的资料：OI Wiki-交互题|猜数（IO交互版）

数据范围

对于10 % 10\%10%的数据，T = 1 T=1T=1；
对于30 % 30\%30%的数据，n ≤ 70 n\le 70n≤70；
对于另外20 % 20\%20%的数据，保证数列a aa随机生成；
对于全部数据：T ≤ 10 , 1 ≤ n ≤ 500 T \leq 10,1\leq n\leq 500T≤10,1≤n≤500。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=510;vector<int>v;intans[N];intask(intx){if(x==1)return1;printf("? 1 %d\n",x);fflush(stdout);intt;scanf("%d",&t);returnt;}intra;intgetmx(intl,intr){if(l==r)returnl;intmid=l+r>>1;intt=ra,tt=ask(mid);if(t==tt){ra=tt;returngetmx(l,mid);}else{ra=t;returngetmx(mid+1,r);}}intmain(){intt,n;scanf("%d",&t);while(t--){scanf("%d",&n);for(inti=n;i;--i){ra=ask(n);intk=getmx(1,n);ans[k]=i;printf("? 2 %d\n",k);fflush(stdout);}printf("!");for(inti=1;i<=n;++i)printf(" %d",ans[i]);puts("");fflush(stdout);}return0;}